# 2007. 从双倍数组中还原原数组
### 题目地址(2007. 从双倍数组中还原原数组)
### 题目描述
```
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
示例 1：
输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
示例 2：
输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。
示例 3：
输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。
提示：
1 <= changed.length <= 105
0 <= changed[i] <= 105
```
### 前置知识
* 哈希表
### 公司
* 暂无
### 思路
由于 0 乘以 2 等于自身，因此这种情况比较特殊，我们先考虑其他一般情况，最后再加 0 这个特判。
由于 changed 中的最小值一定是原数组中的最小值，同理 changed 中的最大值是原数组中的最大值乘以 2.因此实际上，我们可以**确定性得出原数组的两个数**了。
那么剩下的数呢？我们可以利用**贪心消除法**来解决。
即先对 changed 进行排序，并从小到大进行处理。对于 1 <= i <= n - 2， changed\[i] 其可能是原数组中的值，也可能是原数组 double 后的值。但是如果其 `2 * changes[i]` 存在于 changed 中，那么其一定是原数组中的值。
> 这个结论成立的前提是后面讲的 "遇到这样的匹配我们就将匹配的双方消除"。 试想如果基于这种消除的思想这个结论不成立，那么 changes\[i] 一定不会被消除，而只要有一个无法被消除，就是无解的。
这样我们就找到了一对 (changed\[i], `2 * changed[i]`)，将 changes\[i] 加入 ans，并将 `2 * changed[i]` 从 changed 中移除。
算法：
* 对 changed 进行排序，这样从左到右遍历的时候，我们可以确保枚举到的是原数组中的项（成立的前提依旧是上面提到的消除）
* 遍历 changed。 如果 changed\[i] \* 2 存在且可以和 changed\[i] 消除（个数足够，换句话说就是 changed\[i] 数目不大于 changed\[i]\*2 的数目），则进行消除。
如果最后 ans 长度是 changed 一半，说明我们找到了答案，返回即可。否则返回空数组。
### 关键点
* 对 changed 进行排序后再处理
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
counter = collections.Counter(changed)
if counter[0] % 2: return []
n = len(changed)
changed.sort()
ans = []
for c in changed:
if counter[c] < 1: continue
double = c * 2
if double in counter:
ans.append(c)
else:
return []
if double == 0:
counter[double] -= 2
else:
counter[double] -= 1
counter[c] -= 1
if len(ans) == n // 2: return ans
return []
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
### 相关题目
* [5966. 还原原数组](https://leetcode-cn.com/problems/recover-the-original-array/) 2007 和这道题思路类似，都是消除思想。这道题的难点在于 k 是未知的，我们需要先枚举出 k，然后再利用消除思想解决。参考代码：
```py
class Solution:
def recoverArray(self, nums: List[int]) -> List[int]:
n = len(nums)
nums.sort()
for i in range(n):
# enumerate i, assueme that: nums[i] is higher[0]
d = nums[i] - nums[0]
if d == 0 or d & 1: continue # k 应该是大于 0 的整数
k = d // 2
counter = collections.Counter(nums)
ans = []
for key in sorted(counter):
if counter[key + 2 * k] >= counter[key]:
ans += [key + k] * counter[key]
counter[key + 2 * k] -= counter[key]
else:
break # 剪枝（不剪枝的话实测 Python 也能通过，不过要多花很多时间）
if len(ans) == n // 2: return ans
return []
```
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/2007.find-original-array-from-doubled-array.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.