954. 二倍数对数组

题目

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 i + 1] = 2 arr[2 * i]” 时，返回 true；否则，返回 false。

示例 1：

输入：arr = [3,1,3,6]
输出：false

示例 2：

输入：arr = [2,1,2,6]
输出：false

示例 3：

输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

提示：

0 <= arr.length <= 3 * 10^4
arr.length 是偶数
-10^5 <= arr[i] <= 10^5

思路

本以为挺简单的，写了半天没调出来，越调越气，果然思路不对再写都是白搭。

自己的思路是先统计每个数的次数。然后遍历数组，对于每个数找和，看哪个的个数更少，优先使用哪个，但这种策略好像不对，最终挂在了第个用例。

一看官解代码，思路明确，代码简洁，再看自己写的臃肿的还要讨论正负数情况，唉…

正确的思路是，先将数组按绝对值排序，从绝对值最小的开始考虑，因为没有比其绝对值更小的元素了，所以只能和其二倍值组对，如果的个数不少于的，那么继续考虑下一个绝对值次小的，反之返回。

代码

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> nums = new ArrayList<>();
        nums.addAll(map.keySet());
        nums.sort((a, b) -> Math.abs(a) - Math.abs(b));
        for (int num : nums) {
            // 2 * num可能不存在，所以使用getOrDefault，下面同理
            if (map.getOrDefault(2 * num, 0) < map.get(num)) {
                return false;
            }
            map.put(2 * num, map.getOrDefault(2 * num, 0) - map.get(num));
        }
        return true;
    }
}