稀碎从零算法笔记Day52-LeetCode:从双倍数组中还原原数组

题型：数组、贪心

链接：2007. 从双倍数组中还原原数组 - 力扣（LeetCode）

来源：LeetCode

题目描述

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

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

题目样例

代码

测试用例

测试结果

2007. 从双倍数组中还原原数组

已解答

中等

相关企业

提示

一个整数数组 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 <= 105
0 <= changed[i] <= 105

题目思路

让返回没有被X2后的数组那数组的size必然是偶数

为了便于操作可以先将数组排序，然后用一个多重集合记录【X2会得到的数组】——比如遍历到了a[i] 那就将 2*a[i]插入到集合中。当遍历到2*a[i]就将其从集合中减少一次。

最终如果集合不为空，说明不能构成双倍数组，就可以return {};

C++代码

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        // size的个数一定是偶数
        int size = changed.size();
        if(size % 2 == 1)
            return {};
        // 创一个hash 存x2的值
        sort(changed.begin(),changed.end());
        unordered_multiset<int> hash;
        // 插入元素用insert
        // hash.insert(changed[0]);

        vector<int> ans;
        for(int x : changed)
        {
            auto temp = hash.find(x);
            if(temp == hash.end())
            {
                hash.insert(x * 2);
                ans.push_back(x);
            }
            // 如果x在hash中出现过，说明他是某个数的2倍
            else
                hash.erase(temp);
        }
        // for(int temp : ans)
        //     cout<<temp<<" ";
        vector<int> temp;
        // 三目运算符不能放{}
        return hash.empty() ? ans : temp;

    }
};