LeetCode 题解工作台
从双倍数组中还原原数组
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。 给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original 数组，否则请返回空数组。…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们注意到，如果数组 `changed` 是一个双倍数组，那么数组 `changed` 中最小的元素也一定是原数组中的元素，因此，我们可以先对数组 `changed` 进行排序，然后以第一个元素作为起点，从小到大遍历数组 `changed`。 我们使用一个哈希表或数组 来统计数组 `changed` 中每个元素的出现次数。对于数组 `changed` 中的每个元素 ，我们首先检查 是否存在于 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
一个整数数组 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 <= 1050 <= changed[i] <= 105
解题思路
方法一：排序
我们注意到，如果数组 changed 是一个双倍数组，那么数组 changed 中最小的元素也一定是原数组中的元素，因此，我们可以先对数组 changed 进行排序，然后以第一个元素作为起点，从小到大遍历数组 changed。
我们使用一个哈希表或数组 来统计数组 changed 中每个元素的出现次数。对于数组 changed 中的每个元素 ，我们首先检查 是否存在于 中。如果不存在，我们直接跳过这个元素。否则，我们将 减一，并检查 是否存在于 中。如果不存在，我们直接返回一个空数组。否则，我们将 减一，并将 加入答案数组中。
遍历结束后，返回答案数组即可。
时间复杂度 ，空间复杂度 ，其中 为数组 changed 的长度。
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
changed.sort()
cnt = Counter(changed)
ans = []
for x in changed:
if cnt[x] == 0:
continue
cnt[x] -= 1
if cnt[x << 1] <= 0:
return []
cnt[x << 1] -= 1
ans.append(x)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if the candidate is familiar with hash tables and greedy algorithms.
- question_mark
Evaluates how efficiently the candidate uses sorting to solve the problem.
- question_mark
Assesses whether the candidate can handle edge cases, like arrays with odd lengths.
常见陷阱
外企场景- error
Not sorting the array before performing the hash lookup, which could lead to incorrect pairings.
- error
Overlooking edge cases like arrays of odd lengths, which cannot form a valid doubled array.
- error
Failing to check for the presence of the double before removing elements from the hash table, leading to errors.
进阶变体
外企场景- arrow_right_alt
Change the problem to allow multiple instances of the same number in 'original'.
- arrow_right_alt
Instead of sorting, use a priority queue to handle the number pairing more efficiently.
- arrow_right_alt
Extend the problem by checking if the array is 'k-doubled', meaning each element should have a multiple of 'k'.