[LeetCode] 2007. Find Original Array From Doubled Array

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 <= 105
0 <= changed[i] <= 105

从双倍数组中还原原数组。

一个整数数组 original 可以转变成一个 双倍 数组 changed ,转变方式为将 original 中每个元素 值乘以 2 加入数组中,然后将所有元素 随机打乱 。

给你一个数组 changed ,如果 change 是 双倍 数组,那么请你返回 original数组,否则请返回空数组。original 的元素可以以 任意 顺序返回。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-original-array-from-doubled-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这是一道贪心的题目,我参考了这个帖子,思路很清晰。题目给了一个 original 数组和一个 changed 数组,其中 changed 数组理应是 original 数组中每个元素乘以二的结果,请你判断 changed 数组是不是真的符合这个规则。

这道题一定要对 changed 数组排序,或者起码要对 changed 数组中涉及到的每个不同元素进行排序。举个例子,比如 [2, 4, 4, 8] 这个数组,我只有知道最小的元素是 2,我才能确定 4 到底是某个数字的两倍,还是说我需要去找 4 自身的两倍。按照这个例子,我们可以分别找到2和其自身的两倍(4);同时我们遇到第二个 4 的时候,因为现在只剩下一个 4 了,所以他只能被当做那个小的数字,去找是否有一个 8 能与之对应。

具体做法上,这里我用一个 hashmap 记录所有不同元素的出现次数,然后对所有 unique 的 key 进行遍历,看看每个 key 是否能找到他自身的两倍(key + key),如果找不到,或者 key 出现的次数大于 key + key 的话,则返回空的数组。

复杂度

时间O(n + klogk) - 需要对 input 数组排序
空间O(n) - hashmap

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int[] findOriginalArray(int[] changed) {
// corner case
if (changed == null || changed.length % 2 == 1) {
return new int[0];
}

// normal case
int n = changed.length;
Arrays.sort(changed);
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : changed) {
map.put(num, map.getOrDefault(num, 0) + 1);
}

List<Integer> res = new ArrayList<>();
for (int num : changed) {
if (map.get(num) == 0) {
continue;
}
if (map.getOrDefault(num * 2, 0) == 0) {
return new int[0];
}
res.add(num);
map.put(num, map.get(num) - 1);
map.put(num * 2, map.get(num * 2) - 1);
}
return res.stream().mapToInt(i -> i).toArray();
}
}

[LeetCode] 2007. Find Original Array From Doubled Array
https://shurui91.github.io/posts/2604738238.html
Author
Aaron Liu
Posted on
September 18, 2022
Licensed under