【LeetCode题解】2007. 从双倍数组中还原原数组

文章目录

- [2007. 从双倍数组中还原原数组](https://leetcode.cn/problems/find-original-array-from-doubled-array/)
- - - - 思路：
      - 代码：

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

思路：

首先，对输入的 changed 数组进行排序，以便后续操作。
创建一个计数数组 count，数组长度为 changed 数组中最大元素加 1，用于统计每个元素在原始数组中出现的次数。
遍历排序后的 changed 数组，统计每个元素出现的次数，将结果保存在计数数组 count 中。
再次遍历排序后的changed数组，对于每个元素x：
- 如果 x 的计数为 0，则跳过。
- 否则，将 x 的计数减 1，并计算其双倍值 y。
- 如果双倍值 y 超出了计数数组的范围，或者对应的计数为 0，则返回一个空数组。
- 否则，将双倍值 y 的计数减 1，并将 x 添加到结果数组中。
返回结果数组。

代码：

    public static int[] findOriginalArray(int[] changed) {

        Arrays.sort(changed);
        int n = changed.length;
        int[] count = new int[changed[n - 1] + 1];
        for (int x : changed) {
            //统计每个数出现的次数
            count[x]++;
        }
        int[] ans = new int[n >> 1];
        int i = 0;
        for (int x : changed) {
            if (count[x] == 0) {
                continue;
            }
            count[x]--;
            int y = x << 1;
            if (y >=count.length||count[y]<=0){
                return new int[0];
            }
            count[y]--;
            ans[i++] = x;
        }
        return ans;
    }