2007. Find Original Array From Doubled Array 

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
class Solution {
    public int[] findOriginalArray(int[] changed) {
        if ((changed.length & 1) == 1) {
            return new int[0];
        }

        Arrays.sort(changed);
        Queue<Integer> queue = new LinkedList<>(); // 存储原数组中的数字
        int[] ans = new int[changed.length / 2];
        int index = 0;

        for (int c : changed) {
            if (queue.isEmpty() || c != queue.peek() * 2) {
                // queue.isEmpty(), 没有比 c 更小的数字，c 只能存在于原数组
                // c != queue.peek() * 2, c 不能作为双倍数组的元素，只能作为原数组的元素
                queue.offer(c);
            } else {
                // c == queue.peek() * 2, c 为双倍数组的元素，收集原数组元素
                ans[index++] = queue.poll();
                if (index == changed.length / 2) {
                    return ans;
                }
            }
        }

        return new int[0];
    }
}

References

2007. Find Original Array From Doubled Array