[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) - 需要把所有元素放入hashmap + 对 K 个不同元素排序

空间O(n)

Java实现

 1 class Solution {
 2     public int[] findOriginalArray(int[] changed) {
 3         int len = changed.length;
 4         // corner case
 5         if (len % 2 == 1) {
 6             return new int[0];
 7         }
 8 
 9         // normal case
10         int[] res = new int[len / 2];
11         int i = 0;
12         HashMap<Integer, Integer> map = new HashMap<>();
13         for (int num : changed) {
14             map.put(num, map.getOrDefault(num, 0) + 1);
15         }
16         // 这里的排序实际是代替了treemap的作用
17         List<Integer> list = new ArrayList<>(map.keySet());
18         Collections.sort(list);
19         for (int num : list) {
20             if (map.get(num) > map.getOrDefault(num + num, 0)) {
21                 return new int[0];
22             }
23             for (int j = 0; j < map.get(num); j++) {
24                 res[i++] = num;
25                 map.put(num + num, map.get(num + num) - 1);
26             }
27         }
28         return res;
29     }
30 }

LeetCode 题目总结