LeetCode 2007 Find Original Array From Doubled Array

LeetCode

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:

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].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints: 1 <= changed.length <= 10<sup>5</sup>
* 0 <= changed[i] <= 10<sup>5</sup>

题目大意：

给定一个数组，求这个数组是否可以分成两部分，后一部分的每个元素是否前一部分某元素的两倍

解题思路：

由最大值容易确定它的一半是否在数组中。所以排序后由大到小遍历。注意数组元素可能相等，所以不能用visited set来记录已用过的数，val_to_index也不支持重复，只有val_to_count支持

解题步骤：

N/A

注意事项：

1. 用val_to_count，注意遍历时候就要减去，不要进入if才减去

Python代码：

def 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)