题目描述
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
思路
一个简单朴素的思路是对 changed 数组进行排序，然后从小到大做消消乐。具体来说，在排序过后的数组中进行遍历，使用一个哈希表记录被消去的元素的数量。
在遍历时，最小的元素肯定不会被消去，那么它的两倍的数字就会被添加进哈希表中。在遍历到对应的数字时，如果这个数字在哈希表中就给相应的哈希表值减一，减到零时删去哈希表中的元素即可。
最终代码：
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
ct = Counter()
changed.sort()
ans = []
for num in changed:
if num in ct:
ct[num] -= 1
if ct[num] == 0:
del ct[num]
continue
ct[num*2]+=1
ans.append(num)
return [] if ct else ans仔细想想，我们将要被消去的值存放进了哈希表中，而且值的消去是先入先出的，那么我们其实可以用队列代替哈希表（或者说哈希表做到了队列的效果）。
使用队列替代哈希表的做法也很简单，之前是 num 在哈希表中的时候删除，那么我们的做法就是 num 在队列头部的时候弹出。如果在遇到某一个 num 的时候队列非空且 num 的值大于队列首的值，因为后面的值只会大不会小，因此返回代表错误的空列表。
最终代码：
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
dq = deque()
changed.sort()
ans = []
for num in changed:
if dq:
if dq[0] < num:
return []
if dq[0] == num:
dq.popleft()
continue
ans.append(num)
dq.append(num*2)
return [] if dq else ans上面两种方法的时间复杂度都在 的程度，瓶颈都出现在排序中，那么有没有可能不排序呢？当然可以，如果不排序的话，做法类似于 128. 最长连续序列。
首先用一个哈希表 ct 记录所有数字的出现次数，然后用另一个哈希集合 done 表示某个数字是否以及处理完成。遍历 ct 中的 key 进行处理即可。
因为 0 的倍数始终是 0，因此对于要做特殊处理。
而对于其他数字的处理方式是：
- 如果这个数字已经处理完了，跳过；
- 如果这个数字是偶数而且它除二的值在
ct中，跳过； - 否则的话进行处理
- 假设这个数字一共
cnt_num个，它的倍数一共ct[num * 2]个，- 显然当
cnt_num < ct[num * 2]时，还有数字没有对应的双倍，返回空列表； - 等于的话正好匹配完；
- 小于的话还有一些二倍的值。
- 显然当
- 在扩展
ans之后，去处理num的倍数情况，如果正好匹配完的话乘 4，否则就乘 2。
- 假设这个数字一共
最终代码：
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
ct = Counter(changed)
# Process 0
cnt_0 = ct.pop(0, 0)
if cnt_0 % 2 == 1:
return []
ans = [0] * (cnt_0 // 2)
done = set()
for num in ct:
if num in done or (num % 2==0 and num // 2 in ct):
continue
while num in ct:
cnt_num = ct[num]
if cnt_num > ct[num * 2]:
return []
ans.extend([num]*cnt_num)
done.add(num)
if cnt_num < ct[num * 2]:
ct[num * 2]-=cnt_num
num*=2
else:
done.add(num * 2)
num*=4
return ans