954. 二倍数对数组 : 「逐个构造」&「成组构造」&「拓扑排序」

题目描述

这是 LeetCode 上的 954. 二倍数对数组 ，难度为 中等。

Tag : 「优先队列」、「堆」、「构造」、「哈希表」、「拓扑排序」

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个0 <= i < len(arr) / 20<=i<len(arr)/2，都有 arr[2 * i + 1] = 2 * arr[2 * i]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^40<=arr.length<=3∗104
• arr.length 是偶数
• -10^5 <= arr[i] <= 10^5−105<=arr[i]<=105

逐个构造 + 优先队列

整理一下题意：是否能对 arr 进行重组，使得每一个奇数位置的值均是前一个位置的值的两倍，即凑成 \frac{n}{2}2n 组形如 (x, 2 * x)(x,2∗x) 的数对。

对于一个任意的有理数而言，对其乘 22 仅会改变数值的大小，而不会改变其方向（正负性质）。

因此如果我们每次都拿最接近 00 的值作为起点，整个构造过程就是唯一确定的。

具体的，我们可以借助优先队列（堆）来实现，构造一个以与 00 值距离作为基准的小根堆。每次从堆中取出元素 xx，根据当前元素 xx 是否被「预定」过进行分情况讨论：

• 当前值 xx 没有被预定过，说明 xx 必然是数对中的「绝对值」的较小值，此时给 xx 并预定一个 x * 2x∗2，即对 x * 2x∗2 的预定次数加一；
• 当前值 xx 已经被预定过，说明 xx 和此前的某个数 \frac{x}{2}2x 组成过数对，对 xx 的预定次数减一。

当且仅当构成过程结束后，所有数的「预定」次数为 00 时，arr 可以凑成 \frac{n}{2}2n 组形如 (x, 2 * x)(x,2∗x) 的数对。

一些细节：由于 arr[i]arr[i] 的数值范围为 [-10^5, 10^5][−105,105]，同时存在乘 22 操作，因此我们需要对计算结果进行 2 * 10^52∗105 的偏移操作，确保其为正数。

代码：

class Solution {
    static int N = 100010, M = N * 2;
    static int[] cnts = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->Math.abs(a)-Math.abs(b));
        for (int i : arr) q.add(i);
        while (!q.isEmpty()) {
            int x = q.poll(), t = x * 2;
            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;
    }
}
复制代码

• 时间复杂度：令 nn 为 arr 长度，mm 为 arr[i]arr[i] 的值域范围，起始将所有数值放入优先队列（堆）的复杂度为 O(n\log{n})O(nlogn)，从优先队列（堆）中取出并构造复杂度为 O(n\log{n})O(nlogn)，检查构造是否成功复杂度为 O(m)O(m)，整体复杂度为 O(n\log{n} + m)O(nlogn+m)
• 空间复杂度：O(n + m)O(n+m)

成组构造 + 排序 + 预处理剪枝

上述解法中，我们不可避免的对 arr 进行一遍完成的尝试构造，并且在尝试构造结束后再进行一次性的合法性检查。

事实上，如果 arr 能够凑成 \frac{n}{2}2n 组形如 (x, 2 * x)(x,2∗x) 的数对，并且对于某个 xx 可能会出现多次，我们可以统计 arr[i]arr[i] 的数量，并根据绝对值大小进行排序，进行成组构造：cnts[x]cnts[x] 个 xx 消耗 cnts[x]cnts[x] 个 2 * x2∗x。

同时由于我们提前预处理了每个 arr[i]arr[i] 的出现次数，我们可以提前知道是否有 cnts[x]cnts[x] 个 2 * x2∗x 和 xx 成组，从而可以边构造边检查合法性。

代码：

class Solution {
    static int N = 100010, M = N * 2;
    static int[] cnts = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (++cnts[i + M] == 1) list.add(i);
        }
        Collections.sort(list, (a,b)->Math.abs(a)-Math.abs(b));
        for (int i : list) {
            if (cnts[i * 2 + M] < cnts[i + M]) return false;
            cnts[i * 2 + M] -= cnts[i + M];
        }
        return true;
    }
}
复制代码

• 时间复杂度：统计 arr[i]arr[i] 的出现次数以及对 arr[i]arr[i] 去重的复杂度为 O(n)O(n)，对去重数组进行排序的复杂度为 O(n\log{n})O(nlogn)，验证是否合法复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn)
• 空间复杂度：O(n + m)O(n+m)

成组构造 + 拓扑排序

对于上述两种解法，要么利用「优先队列」要么利用「排序」，目的都是为了找到数对中的「绝对值较小」的那一位，然后开始往后构造。

事实上，我们可以利用任意 xx 只可能与 \frac{x}{2}2x 或者 2 * x2∗x 组成数对来进行建图，通过对图跑拓扑序来验证是否能够凑成 \frac{n}{2}2n 组形如 (x, 2 * x)(x,2∗x) 的数对。

不了解「拓扑排序」的同学可以看前置 🧀：图论拓扑排序入门，里面通过图解演示了何为拓扑序，以及通过「反证法」证明了为何有向无环图能够能够进行拓扑排序。

特别的，我们需要特殊处理 arr[i] = 0arr[i]=0 的情况，由于 00 只能与本身组成数对，为了避免自环，我们需要跳过 arr[i] = 0arr[i]=0 的点，同时特判 arr[i] = 0arr[i]=0 的出现数量为奇数时，返回无解。

和解法二一样，先对 arr[i]arr[i] 进行数量统计以及去重预处理（跳过 00），然后对去重数组 list 中出现的数值 xx 进行分情况讨论：

• xx 为奇数，由于 \frac{x}{2}2x 不为整数，因此 xx 只能作为数对中绝对值较小的那个（即 xx 入度为 00），加入队列；
• xx 为偶数，首先令 xx 的入度 in[x] = cnts[\frac{x}{2}]in[x]=cnts[2x]，代表有 cnts[\frac{x}{2}]cnts[2x] 个 \frac{x}{2}2x 与其对应。当 in[x] = 0in[x]=0 时，说明没有 \frac{x}{2}2x 与其成对，此时 xx 只能作为数对中绝对值较小的那个（即 xx 入度为 00），加入队列。

跑一遍拓扑排序，假设当前出队值为 tt，此时需要消耗掉 cnts[t]cnts[t] 个 t * 2t∗2 与其形成数对（即 cnts[t * 2] -= cnts[t]cnts[t∗2]−=cnts[t] ），同时 t * 2t∗2 的入度也要更新（即可 in[t * 2] -= cnts[t]in[t∗2]−=cnts[t] ），若 in[t * 2] = 0in[t∗2]=0 且此时 cnts[t * 2] > 0cnts[t∗2]>0，将 t * 2t∗2 进行入队。同时由于我们明确减少了 t * 2t∗2 的数量，因此需要同步更新 t * 4t∗4 的入度，同理，当 t * 4t∗4 的入度 in[t * 4] = 0in[t∗4]=0，同时 cnts[t * 4] > 0cnts[t∗4]>0 时，需要将 t * 4t∗4 进行入队。

代码：

class Solution {
    static int N = 100010, M = 2 * N;
    static int[] cnts = new int[M * 2], in = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        Arrays.fill(in, 0);
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (++cnts[i + M] == 1 && i != 0) list.add(i);
        }
        if (cnts[M] % 2 != 0) return false;
        Deque<Integer> d = new ArrayDeque<>();
        for (int i : list) {
            if (i % 2 == 0) {
                in[i + M] = cnts[i / 2 + M];
                if (in[i + M] == 0) d.addLast(i);
            } else { 
                d.addLast(i);
            }
        }
        while (!d.isEmpty()) {
            int t = d.pollFirst();
            if (cnts[t * 2 + M] < cnts[t + M]) return false;
            cnts[t * 2 + M] -= cnts[t + M];
            in[t * 2 + M] -= cnts[t + M];
            if (in[t * 2 + M] == 0 && cnts[t * 2 + M] != 0) d.addLast(t * 2);
            in[t * 4 + M] -= cnts[t + M];
            if (in[t * 4 + M] == 0 && cnts[t * 4 + M] != 0) d.addLast(t * 4);
        }
        return true;
    }
}
复制代码

• 时间复杂度：统计数量和入度的复杂度为 O(n)O(n)；跑拓扑序验证的复杂度为 O(n)O(n)。整体复杂度为 O(n)O(n)
• 空间复杂度：O(n + m)O(n+m)

相关阅读

图论拓扑排序入门：通过图解演示了何为拓扑序，以及通过「反证法」证明了为何有向无环图能够能够进行拓扑排序 🎉 🎉

最后

这是我们「刷穿 LeetCode」系列文章的第 No.954 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。