<div>
An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.
Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.
Example 1:
<pre>Input: changed = [1,3,4,2,6,8] Output: [1,3,4] Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8. Other original arrays could be [4,3,1] or [3,1,4]. </pre>
Example 2:
<pre>Input: changed = [6,3,0,1] Output: [] Explanation: changed is not a doubled array. </pre>
Example 3:
<pre>Input: changed = [1] Output: [] Explanation: changed is not a doubled array. </pre>
Constraints:
1 <= changed.length <= 10<sup>5</sup>0 <= changed[i] <= 10<sup>5</sup>
</div>
题目大意：
给定一个数组，求这个数组是否可以分成两部分，后一部分的每个元素是否前一部分某元素的两倍
解题思路：
由最大值容易确定它的一半是否在数组中。所以排序后由大到小遍历。注意数组元素可能相等，所以不能用visited set来记录已用过的数，val_to_index也不支持重复，只有val_to_count支持
解题步骤：
N/A
注意事项：
- 用val_to_count，注意遍历时候就要减去，不要进入if才减去
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def findOriginalArray(self, changed: List[int]) -> List[int]:
if len(changed) % 2 == 1:
return []
changed.sort()
res = []
val_to_count = collections.Counter(changed)
for i in reversed(range(len(changed))):
if val_to_count[changed[i]] == 0:
continue
val_to_count[changed[i]] -= 1 # not in if statement
if changed[i] / 2 in val_to_count and val_to_count[changed[i] / 2] > 0:
val_to_count[changed[i] / 2] -= 1
res.append(int(changed[i] / 2))
return [] if len(res) * 2 != len(changed) else res
算法分析：
时间复杂度为O(nlogn)，空间复杂度O(n)
