跳到主要内容

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

链接：2007.从双倍数组中还原原数组
难度：Medium
标签：贪心、数组、哈希表、排序
简介：给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

题解 1 - python​

  • 编辑时间：2024-04-18
  • 执行用时：194ms
  • 内存消耗：32.71MB
  • 编程语言：python
  • 解法介绍：哈希存储后遍历。
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        map = Counter(changed)
        arr = sorted(map.keys())
        res = []
        for num in arr:
            if map[num] == 0: continue
            if num == 0:
                if map[num] % 2 != 0: return []
                res += [0] * (map[num] // 2)
                continue
            if map[num] > map[num * 2]: return []
            map[num * 2] -= map[num]
            res += [num] * map[num]
        return res