※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: 2007. Find Original Array From Doubled Array
: 题目：给定一个阵列，若该阵列可以由某个阵列的所有元素乘2之后组合成，我们
: 说这个阵列是一个 Doubled Array，找出这个阵列是否是 Doubled Array 若存在则
: 返回该阵列变成 Doubled Arraay前的阵列。
: Example:
: [1,3,4] => [1,3,4,2,6,8]
思路：
1.反正先sort 从最小元素的开始删别人 找不到两倍的自己就不是doubled array
[1,3,4,2,6,8] -> [1,2,3,4,6,8] ->检查1*2有没有在array里 有就删掉
2.不想每次都O(n)查 所以把预计要删的元素存成deque
每次检查最小的那个能不能删就好(检查deque[0])
删不掉就尝试去删别人(deque.append())
这里可以再判断如果deque[0]*2比你小就直接失败 因为没人能和他配了
3.最后看预计要删的元素是不是空的
Python Code:
from collections import deque
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
changed.sort()
doubles = deque()
origin = []
for value in changed:
if doubles and doubles[0]*2 == value:
origin.append(doubles.popleft())
else:
doubles.append(value)
return origin if not doubles else []