目标
一个整数数组 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 <= 10^5
- 0 <= changed[i] <= 10^5
思路
所谓双倍数组指的是由原数组以及其每个元素乘以2之后的元素合并在一起的数组。现在想要从双倍数组还原为原数组，如果不是合法的双倍数组则返回空数组。
首先，如果元素个数为奇数肯定不是双倍数组。注意到数组中的元素如果是奇数那么一定属于原数组。由于返回数组的顺序任意，那么先排序会更好处理。
接着就想到将奇数与偶数分开，然后看奇数*2是否有相应的偶数对应，或者可以将偶数元素/2看是否有奇数对应（不过这样就得处理0的情况，因为0只能与它自己匹配）。匹配完成后可能还剩下原数组中的偶数元素与其对应的双倍元素。
该如何处理呢？看了具体的例子很容易有一些想当然的想法，比如剩余[2,2,4,4]很容易将其平分为两部分，然后同时比较这两部分相应的位置是否满足二倍关系。这种假设是没有根据的，也是不对的，比如剩余[2、2、4、4、4、6、8、12]也是合法的。那我们该怎么比较呢？
这时突然有一个想法出现在大脑中，可以先将当前元素存到队列中，如果后面的元素不是其二倍就添加到队列中，如果是则将队列的第一个元素取出，这样遍历完之后看队列中是否还有数据即可。我们之所以可以这么做是因为前面排过序了，队首元素的二倍元素一定会最先出现。如果不排序的话，比如说[2,1]，2先加入队列，后加入的1就无法匹配了。再比如[4,8,2,16]，4与8匹配了，剩下的就匹配不了了。
有了这个想法之后，前面区分奇数、偶数，对0做特殊处理就都没有必要了。
网友还介绍了一种消消乐的方法，可以不排序。这个需要先统计各元素出现的次数，然后如果x % 2 == 0 && cnt.containsKey(x / 2)则跳过，即如果 x/2 在 cnt 中，则跳过，直到找到开始的那个x，然后一次性处理之前被跳过的2x、4x、6x...。这里其实也利用了顺序，只不过没有排序而是先找到不能再分的那个初始节点再向后倍增。
还有的使用大数组保存了 0~max 元素出现次数的数组cnt，然后遍历cnt，如果cnt[i]>0 而 2*i>max || cnt[2i]==0 直接返回空数组，否则cnt[2i]--。这个方法也不用排序，是因为统计个数时变相地将数组元素映射为下标，遍历cnt数组是从小到大有序的。
代码
/**
* @date 2024-04-18 8:48
*/
public class FindOriginalArray2007 {
public int[] findOriginalArray(int[] changed) {
int n = changed.length;
if (n % 2 == 1) {
return new int[0];
}
Arrays.sort(changed);
int originLength = n / 2;
int[] res = new int[originLength];
Deque<Integer> collect = new ArrayDeque<>();
int i = 0;
for (int j = 0; j < changed.length; j++) {
if (collect.size() == 0 || changed[j] % 2 == 1 || !collect.peek().equals(changed[j] / 2)) {
collect.add(changed[j]);
} else {
res[i++] = collect.poll();
}
}
if (collect.size() > 0) {
return new int[0];
}
return res;
}
}
性能
