LC.P954[二倍数对数组]

方法一：排序+哈希表

先用哈希表记录数组中每个元素出现的次数，将哈希表中的key(即数组中不同的元素)放入List中，对List进行排序后：

记当前元素为x(对一个有理数而言，乘$2$劲会改变数的大小，不会改变数的正负)

  1. 若$x > 0$，且$2 * x$出现的次数小于$x$出现的次数，则无法组成二倍数对数组；否则，可以配对，$将2 * x$出现的次数减去$x$出现的次数
  2. 若$x = 0$，因为$2 * x = 0$，需要特殊处理，判断$0$出现的次数是否为偶数
  3. 若$x < 0$，因为$x$按升序排列，所以当前$x$需要与$x / 2$配对(例如：$-4$与$-2$配对)，注意：需要判断当前元素出现的次数是否大于$0$，例如：[-4, -2, 2, 4]，遍历$-4$时，与$-2$配对，$-2$出现的次数变为$0$，已配对完成，若不加cnt > 0，则会在map.put(key / 2, map.get(key / 2) - cnt);报错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : arr) map.merge(n, 1, Integer::sum);
        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((a, b) -> a - b);
        for (int key : list) {
            int cnt = map.get(key);
            
            if (key > 0) {
                if (map.getOrDefault(2 * key, 0) < cnt) return false;
                if (cnt > 0) map.put(2 * key, map.get(2 * key) - cnt);
            } else if (key == 0) { // 对 0 特殊处理
                if (map.get(key) % 2 != 0) return false;
            } else {
                if (cnt > 0) {
                    if ((key % 2 != 0 || map.getOrDefault(key / 2, 0) < cnt)) return false;
                    map.put(key / 2, map.get(key / 2) - cnt);
                }
            }
        }
        return true;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$

方法二：排序+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : arr) map.merge(x, 1, Integer::sum);
        // 0只能与0配对
        if (map.getOrDefault(0, 0) % 2 != 0) return false;
        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((a, b) -> Math.abs(a) - Math.abs(b));
        for (int x : list) {
            int cnt = map.get(x);
            if (map.getOrDefault(2 * x, 0) < cnt) return false;
            map.put(2 * x, map.getOrDefault(2 * x, 0) - cnt);
        }
        return true;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$