lc954. 二倍数对数组（优先队列）

给定一个长度为偶数的整数数组 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 * 104
arr.length 是偶数
-105 <= arr[i] <= 105

class Solution {
    //找成对出现的两倍关系的数值对,用小根堆存储各个数的绝对值，最先碰到的肯定是小的，然后用cnts数组记录乘以2的数量，最后判断cnts数组是否为0，注意偏移量
    static int N = 100010, M = N * 2;
    static int[] cnts = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        int n = arr.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Math.abs(a) - Math.abs(b));
        for (int i : arr) pq.add(i);
        while (!pq.isEmpty()) {
            int x = pq.poll(), t = x * 2;
            //判断是不是组合第二个数(乘以2的),是就构成了组合，continue
            if (cnts[x + M] > 0 && --cnts[x + M] >= 0) continue;
            cnts[t + M] ++;
        }
        for (int i = 0; i < M * 2; ++i) 
            if (cnts[i] != 0) return false;
        return true;
    }
}