哈希，LeetCode 2007. 从双倍数组中还原原数组

一、题目

1、题目描述

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

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

2、接口描述

python3

​

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:

cpp

​

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {

    }
};

3、原题链接

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

二、解题报告

1、思路分析

我们考虑将数组排序后会是什么样子？

a ... a  2a... 2a  c ... c  d ... d 2d ……

那么我们有一种O(nlogn)做法（也是我第一次做的时候的做法），将数组排序，然后哈希统计

然后从小到大遍历数组，用x排除2x，如果出现某个元素仍有剩余那就返回空，不然就是一个目标数组，我们在遍历的时候添加元素到返回数组即可

然后看到题解有O(n)做法

事实上不需要排序，只需哈希计数

我们发现我们只要拿到a，就能排除2a，4a……

那么我们哈希 统计后，遍历哈希表，如果x不存在x / 2在哈希表中，说明它可能是某个连续序列的起点，我们从x往下一直排除2x，4x……

如果存在cnt[x] > cnt[2x]就返回空数组

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

3、代码详解

python3

​

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        mp = Counter(changed)
        cnt0 = mp.pop(0, 0) # default = 0，不存在0返回0
        if cnt0 & 1:
            return []
        ret = [0] * (cnt0 // 2)
        for x in mp:
            if x % 2 == 0 and x // 2 in mp:
                continue
            while x in mp:
                cnt = mp[x]
                if cnt > mp[x * 2]:
                    return []
                ret.extend([x] * cnt)
                if cnt < mp[x * 2]:
                    mp[x * 2] -= cnt
                    x *= 2
                else:
                    x *= 4
        return ret

        

cpp

​

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        if(changed.size() & 1) return {};
        unordered_map<int, int> mp;
        int cnt0 = 0;
        for(auto x : changed) mp[x] ++, cnt0 += !x;
        if(cnt0 & 1) return {};
        mp.erase(0);
        vector<int> ret(cnt0 / 2);
        for(auto [k, _] : mp){
            int x = k;
            if(x & 1 || !mp.count(x / 2)){
                while(mp.count(x)){
                    int cnt = mp[x];
                    if(cnt > mp[x * 2]) return {}; 
                    ret.insert(ret.end(), cnt, x);
                    if(mp[x << 1] > cnt) mp[x << 1] -= cnt, x <<= 1;
                    else x <<= 2;
                }
            }
        }
        return ret;
    }
};