LeetCode 2007. 从双倍数组中还原原数组（map）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

示例 1： 输入：changed = [1,3,4,2,6,8] 输出：[1,3,4] 解释：一个可能的 original 数组为 [1,3,4] : - 将 1 乘以 2 ，得到 1 * 2 = 2 。 - 将 3 乘以 2 ，得到 3 * 2 = 6 。 - 将 4 乘以 2 ，得到 4 * 2 = 8 。 其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。示例 2： 输入：changed = [6,3,0,1] 输出：[] 解释：changed 不是一个双倍数组。示例 3： 输入：changed = [1] 输出：[] 解释：changed 不是一个双倍数组。提示： 1 <= changed.length <= 10^5 0 <= changed[i] <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-original-array-from-doubled-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 数组长度需要为偶数
• map计数，map有序，每次取出 begin 的数值 x，查找是否存在 2*x，计数为0时，删除元素

class Solution { public:vector<int> findOriginalArray(vector<int>& changed) {if(changed.size()%2==1) return {};map<int,int> m;for(auto n : changed)m[n]++;vector<int> ans(changed.size()/2);int i = 0;while(!m.empty()){int x = m.begin()->first;if(--m[x] == 0)m.erase(x);if(m.find(2*x) != m.end()){if(--m[2*x] == 0)m.erase(2*x);ans[i++] = x;}elsereturn {};}return ans;} };

400 ms 140.6 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 2007. 从双倍数组中还原原数组（map）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。