LeetCode 2007. 从双倍数组中还原原数组

题目链接

https://leetcode.cn/problems/find-original-array-from-doubled-array/description/?envType=daily-question&envId=2024-04-18

先给数组排序，然后使用hashmap来标记元素是双倍之前还是之后的

class Solution {
    public int[] findOriginalArray(int[] changed) {
        Arrays.sort(changed);
        int[] ans = new int[changed.length / 2];
        int j = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<changed.length;i++) {
            int x = changed[i];
            if (!map.containsKey(x)) { //当前元素x不是双倍后的
                if (j == ans.length) {
                    return new int[0];
                }
                ans[j] = x;
                j++;
                map.merge(x * 2, 1, Integer::sum); //标记
            } else { //当前元素x是双倍后的
                int c = map.merge(x, -1, Integer::sum); //清除标记
                if (c == 0) {
                    map.remove(x);
                }
            }
        }
        return ans;
    }
}