【面试高频题】多解法高频构造题

题目描述

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

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

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2 ，都有arr[2 \times i + 1] = 2 \times arr[2 \times 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]

提示：

• arr.length 是偶数

逐个构造 + 优先队列

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

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

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

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

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

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

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

代码：

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;
    }
}

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

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

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

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

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

代码：

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] 去重的复杂度为 O(n) ，对去重数组进行排序的复杂度为 O(n\log{n}) ，验证是否合法复杂度为 O(n) 。整体复杂度为O(n\log{n})
• 空间复杂度：

成组构造 + 拓扑排序

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

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

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

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

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

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

跑一遍拓扑排序，假设当前出队值为 t ，此时需要消耗掉 cnts[t] 个 t \times 2 与其形成数对（即 cnts[t \times 2] -= cnts[t] ），同时 t \times 2 的入度也要更新（即 in[t \times 2] -= cnts[t] ），若 in[t \times 2] = 0 且此时 cnts[t \times 2] > 0，将 t \times 2 进行入队。同时由于我们明确减少了 t \times 2 的数量，因此需要同步更新 t \times 4 的入度，同理，当 t \times 4 的入度 in[t \times 4] = 0 ，同时 cnts[t \times 4] > 0 时，需要将 t \times 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)
• 空间复杂度：

最后

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

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

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

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