LeetCode-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 <= 10⁵
0 <= changed[i] <= 10⁵

解题思路一：排序 + 哈希表

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        changed.sort()
        ans = []
        cnt = Counter()
        for x in changed:
            if x not in cnt:  # x 不是双倍后的元素
                cnt[x * 2] += 1 # 标记一个双倍元素
                ans.append(x)
            else: # x 是双倍后的元素
                cnt[x] -= 1 # 清除一个标记
                if cnt[x] == 0:
                    del cnt[x]
        # 只有所有双倍标记都被清除掉，才能说明 changed 是一个双倍数组
        return [] if cnt else ans

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

解题思路二：排序 + 队列

在方法一中，我们是小到大遍历 x=changed[i]的，所以加到哈希表中的 2x（双倍标记）也是从小到大的，并且最先加到哈希表中的双倍标记，也会最先清除掉。这种「先进先出」的性质启发我们把哈希表替换成更轻量的队列，队首就是下一个等待被清除的双倍标记。

具体来说，在循环中：

1. 如果队列为空，把 x 加入答案，把 2x 加入队尾。如果后面遍历到一个等于 2x 的元素，则说明 x 和 2x 都在数组中，配对成功。
2. 如果队列不为空，并且队首小于 x，由于后面遍历到的数只会更大，所以队首无法配对，返回空数组。
3. 如果队列不为空，并且队首等于 x，配对成功，弹出队首。
4. 如果队列不为空，并且队首大于 x，把 x 加入答案，把 2x 加入队尾。

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        changed.sort()
        ans = []
        q = deque()
        for x in changed:
            if q:
                if q[0] < x:  # 无法配对
                    return []
                if q[0] == x:  # 配对成功
                    q.popleft()  # 清除一个标记
                    continue
            ans.append(x)
            q.append(x * 2)  # 添加双倍标记
        # 只有所有双倍标记都被清除掉，才能说明 changed 是一个双倍数组
        return [] if q else ans

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

解题思路三：消消乐

在给定的代码中，pop(0, 0)是一种使用Counter对象的方法。Counter是Python中的一个内置类，用于计数可哈希对象（例如列表、元组、字符串等）中元素的出现次数。

让我们分解这个代码片段：

cnt = Counter(changed): 这一行创建了一个Counter对象cnt，并使用changed中的元素对其进行初始化。这意味着cnt对象将会统计changed中每个元素的出现次数。
cnt0 = cnt.pop(0, 0): 这一行调用了cnt对象的pop方法，并传递了两个参数。pop方法用于从Counter对象中移除并返回指定键的元素，如果键不存在，则返回指定的默认值。具体来说：

• 第一个参数0是要移除的键，即从cnt中移除键为0的元素。
• 第二个参数0是默认值，表示如果键不存在，则返回0。

因此，pop(0, 0)这个操作的意思是从cnt中移除键为0的元素，如果键不存在，则返回0。

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        cnt = Counter(changed)
        # 单独处理 0
        cnt0 = cnt.pop(0, 0)
        print(cnt0)
        if cnt0 % 2:
            return []
        ans = [0] * (cnt0 // 2)

        done = set()
        for x in cnt:
            # 如果 x 已处理完毕，或者 x/2 在 cnt 中，则跳过
            if x in done or x % 2 == 0 and x // 2 in cnt:
                continue
            # 把 x, 2x, 4x, 8x, ... 全部配对
            while x in cnt:
                # 每次循环，把 cnt_x 个 x 和 cnt_x 个 2x 配对
                cnt_x = cnt[x]
                # 无法配对，至少要有 cnt_x 个 2x
                if cnt_x > cnt[x * 2]:
                    return []
                ans.extend([x] * cnt_x)
                # x 配对完成
                done.add(x)
                if cnt_x < cnt[x * 2]:
                    # 还剩下一些 2x
                    cnt[x * 2] -= cnt_x
                    x *= 2
                else:
                    # 2x 配对完成
                    done.add(x * 2)
                    x *= 4
        return ans

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