LeetCode 954. 二倍数对数组

2022-03-02 HGNULB 约 11 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 954. 二倍数对数组

题意分析

给一个长度为偶数的整数数组 arr，问能否重新排列它，使得对每个 i（0 <= i < n/2）都有 arr[2i + 1] = 2 * arr[2i]。

「重新排列」这个说法容易让人以为要真的构造出排列，其实它等价于一个更简单的问题：能否把数组的所有元素两两配对，使每一对都形如 (x, 2x)。因为配对之后按对摆放即可，摆放本身没有难度。所以本题的实质是完美匹配的存在性判定。

关键约束有三条。第一，元素可以是负数，-4 与 -2 也构成合法的 (x, 2x) 对（-4 = 2 × (-2)）——注意这里较小的那个是 -2 而不是 -4，负数一侧的「倍数关系」在数值上是往更小走的，这直接决定了处理顺序不能简单按数值升序。第二，元素可以是 0，而 0 = 2 × 0，所以 0 只能和 0 配对，其个数必须是偶数。第三，元素可以重复，所以要按出现次数处理而不是按去重后的集合。

数据规模上 n 不超过 $3 \times 10^4$，元素绝对值不超过 $10^5$。规模允许 $O(n \log n)$，但不允许 $O(n^2)$ 的两两枚举匹配。同时值域有界也提示可以用哈希计数而不是排序整个数组。

边界要留意：arr 长度为奇数在本题约束下不会出现（题面保证偶数），但计数不匹配的情况必须能被检出；另外 2 * x 可能不在数组里，此时该 x 无处可配，直接失败。

解法：排序 + 贪心

核心思路

暴力想法是搜索：枚举第一个元素与谁配对，递归处理剩下的。这是指数级的，$n = 30000$ 完全不可行。

瓶颈在于「谁和谁配对」看似有选择空间。但仔细想会发现选择其实并不自由。考察绝对值最小的那个非零元素 x：它能参与的对只有 (x/2, x) 和 (x, 2x) 两种，而 x/2 的绝对值比 x 更小，与「x 是绝对值最小」矛盾，所以 x 只能作为对中较小的那个，必须去配 2x。这就没有选择了——它是被逼的。

把 x 和对应数量的 2x 一起删掉之后，剩下的子问题结构完全相同，于是可以归纳地重复这个论证。这就给出了贪心的正确性：按绝对值从小到大处理每个值 x，让它全部去配 2x。这个顺序保证了每次处理到 x 时，所有绝对值更小的值都已消耗完毕，x 必然是当前剩余里的「最小」，因而它的配对方式唯一。

之所以按绝对值而不是数值排序，正是为了让正负两侧统一。对正数 x，2x 的绝对值更大；对负数 x，2x 更小（数值上）但绝对值同样更大。用 |x| 升序排序，两侧都满足「先处理配对中较小的那一半」。

状态就是一张计数表 count，count[v] 表示值 v 还有多少个未被配对。维持的不变量是：当按绝对值升序处理到某个 x 时，所有绝对值小于 |x| 的值的计数都已归零；因此 count[x] 就是必须立刻全部配掉的数量，而它们只能配给 count[2x]。若 count[2x] < count[x]，说明存在无处可配的 x，整个数组不可能完成配对，直接失败。

0 是唯一的例外：2 × 0 = 0，它只能和自己配，所以判定条件是「个数为偶数」，处理完直接清零。把 0 混进通用分支会导致自己配自己的逻辑混乱，必须单独拆出来。

解题步骤

统计频次：用哈希表 count 记录每个值出现的次数。为什么不直接排序整个数组：重复元素很多时按值批量处理更省事，而且「一次性把 count[x] 个 x 全配掉」的写法比逐个匹配更贴近贪心的证明。

取出所有不同的键，按 |key| 升序排序：这是贪心成立的前提。排序的对象是去重后的键而不是原数组，规模更小。为什么必须用绝对值：负数一侧的 (x, 2x) 中 2x 在数值上更小，若按数值升序会先处理 -4 再处理 -2，而 -4 应该由 -2 来消耗，顺序一反就永远配不上。

跳过已被消耗完的键：若 count[x] == 0 直接 continue。为什么会出现 0：x 可能在处理更小的 x/2 时就被全部消耗掉了，此时它不该再发起配对。

单独处理 0：若 count[0] 为奇数返回 false，否则置零继续。为什么不能走通用分支：通用分支会去查 count[2 * 0] = count[0]，即拿自己和自己比，条件恒成立，从而放过奇数个 0 的非法输入。

通用配对：令 y = 2 * x，若 count[y] < count[x] 返回 false；否则 count[y] -= count[x]，再把 count[x] 置零。为什么是「全部一起配」而不是逐个：由不变量可知这些 x 只有 y 一个去处，逐个配和批量配结果相同，批量写法更短且不易漏。为什么配完要清零：标记这些 x 已消耗，防止后续被重复使用。

全部键处理完返回 true：每个值都成功找到了归宿，配对存在。

以 arr = [4, -2, 2, -4] 走一遍。计数为 {4:1, -2:1, 2:1, -4:1}，键按绝对值升序为 2, -2, 4, -4（绝对值相同的两个键先后顺序不影响结果，因为它们的目标 2x 互不相同）。
处理 2：count[2] = 1 非零，非 0 分支，y = 4，count[4] = 1 >= 1，于是 count[4] 变 0、count[2] 变 0。
处理 -2：count[-2] = 1，y = -4，count[-4] = 1 >= 1，count[-4] 变 0、count[-2] 变 0。
处理 4：count[4] 已是 0，跳过。
处理 -4：同样是 0，跳过。
返回 true，对应排列 [2, 4, -2, -4]，符合要求。

再看反例 arr = [3, 1, 3, 6]。计数 {3:2, 1:1, 6:1}，键按绝对值升序为 1, 3, 6。
处理 1：y = 2，count[2] = 0 < 1，立即返回 false。确实——1 只能和 2 配，而数组里没有 2。

再看 arr = [0, 0, 0, 1] 这类含 0 的输入：计数 {0:3, 1:1}，键按绝对值升序为 0, 1。处理 0 时发现 count[0] = 3 为奇数，直接返回 false；若没有这条特判，通用分支会算 y = 0、count[0] = 3 >= 3 成立而放行，得出错误的 true。

代码实现

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : arr) {
            count.merge(x, 1, Integer::sum);
        }

        // 按绝对值升序，保证每次处理的都是配对中较小的那一半。
        Integer[] keys = count.keySet().toArray(new Integer[0]);
        Arrays.sort(keys, Comparator.comparingInt(Math::abs));

        for (int x : keys) {
            int cnt = count.getOrDefault(x, 0);
            if (cnt == 0) {
                continue;
            }
            // 0 只能和 0 配，个数必须成双。
            if (x == 0) {
                if ((cnt & 1) == 1) {
                    return false;
                }
                count.put(x, 0);
                continue;
            }

            int y = x * 2;
            if (count.getOrDefault(y, 0) < cnt) {
                return false;
            }
            count.put(y, count.get(y) - cnt);
            count.put(x, 0);
        }

        return true;
    }
}

func canReorderDoubled(arr []int) bool {
    count := make(map[int]int)
    for _, x := range arr {
        count[x]++
    }

    keys := make([]int, 0, len(count))
    for k := range count {
        keys = append(keys, k)
    }
    // 按绝对值升序，保证每次处理的都是配对中较小的那一半。
    sort.Slice(keys, func(i, j int) bool {
        return abs954(keys[i]) < abs954(keys[j])
    })

    for _, x := range keys {
        cnt := count[x]
        if cnt == 0 {
            continue
        }

        // 0 只能和 0 配，个数必须成双。
        if x == 0 {
            if cnt%2 != 0 {
                return false
            }
            count[x] = 0
            continue
        }

        y := x * 2
        if count[y] < cnt {
            return false
        }
        count[y] -= cnt
        count[x] = 0
    }

    return true
}

func abs954(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

复杂度分析

时间复杂度：$O(n \log n)$。凭什么：统计频次是 $O(n)$；设不同值的个数为 k（$k \le n$），对键按绝对值排序是 $O(k \log k)$，这是主导项；主循环每个键只处理一次，每次做常数次哈希查询与更新，合计 $O(k)$。

空间复杂度：$O(n)$。凭什么：哈希表最多存 k 个不同值，键数组同样 k 个元素，最坏情况下所有元素互不相同即 $k = n$。

关键点总结

「能否重排使得满足某种配对形式」通常等价于「完美匹配是否存在」，先把题面从构造问题翻译成判定问题，思路会立刻变清晰。

贪心的正确性论证套路是找「无选择的元素」：绝对值最小的非零元素只能当对中较小者，选择唯一，删掉它之后子问题同构，于是归纳成立。凡是贪心题，能说出这套论证才算真的会。

涉及负数的倍数关系时，排序键要用绝对值而不是数值，这样正负两侧的「较小者先处理」可以统一，避免写两套逻辑。

自身构成不动点的取值（这里是 0，其他题里可能是 1 或空串）几乎总要单独分支，因为通用逻辑会把它和自己比较从而恒真。

按频次批量处理比逐元素匹配更简洁，前提是先证明「这一批只有唯一去处」。

面试视角：写完代码后主动说明两点——为什么按绝对值排序（举 [-4,-2] 说明按数值排序会失败）、为什么 0 要特判（举 [0,0,0,1]）。这两个反例就是面试官的检验点；若被追问优化，可以提「值域只有 $2 \times 10^5$，可以用桶代替哈希表把排序省成计数排序，做到 $O(n + U)$」。

易错点总结

错误写法：按数值升序而不是绝对值升序排序键 → 用例 arr = [4,-2,2,-4] 会先处理 -4，去找 -8 找不到，返回 false，而正确答案是 true。

错误写法：漏掉 x == 0 的特判 → 用例 arr = [0,0,0,1] 中通用分支拿 count[0] >= count[0] 自比恒成立，奇数个 0 被放行，返回 true，正确答案是 false。

错误写法：0 的判定写成 cnt < 2 而不是奇偶 → 用例 arr = [0,0,0,0,0,1,...] 中五个 0 通过了「至少两个」的检查，实际剩下一个 0 无处可配。

错误写法：不跳过 count[x] == 0 的键 → 用例 arr = [1,2,2,4] 中 2 已被 1 消耗完，若仍以 cnt = 0 进入通用分支虽不报错，但一旦把条件写成 count[y] <= cnt 就会误判；更严重的是若忘记配对后清零，2 会被重复用来配 4，得到错误的 true。

错误写法：配对成功后忘记把 count[x] 清零 → 用例 arr = [1,2,2,4] 中值 2 先被 1 消耗，再作为键发起配对去消耗 4，一个元素被用了两次，非法输入会被判为合法。

错误写法：配对条件写成 count[y] > 0 而不是 count[y] >= cnt → 用例 arr = [2,2,4,8] 中两个 2 只有一个 4 可配，条件却成立，返回 true，正确答案是 false。

错误写法：用 count.get(y) 而不先判存在性 → 用例 arr = [1,3] 中 count.get(2) 在 Java 里返回 null，自动拆箱抛空指针异常；Go 的 map 取不存在的键返回零值不会崩，但两份代码行为要一致。

错误写法：直接对原数组 arr 排序后用双指针从两端配对 → 用例 arr = [4,-2,2,-4] 排序后为 [-4,-2,2,4]，两端 -4 与 4 并不构成倍数关系，双指针模型在这题根本不成立。

错误写法：把配对方向写反，让 x 去消耗 x / 2 → 用例 arr = [1,2] 中处理 1 时找 0（整数除法）找不到，返回 false；即使改成只在偶数时才找 x/2，也会因为处理顺序不对而在 [2,4] 上失败。

错误写法：用 x << 1 求 2x 但把 x 声明成 short 或在乘法前做了截断 → 用例中元素达 $10^5$ 时 2x 溢出成负数，配对表查询到错误的桶。

错误写法：忘记数组元素可能重复，用 Set 而不是计数表 → 用例 arr = [2,2,4,4] 中去重后只剩 {2,4}，无法反映数量关系，[2,2,4,8] 这类输入也会被误判为合法。

相似题目

题目	难度	考察点
1497. 检查数组对是否可以被 k 整除	中等	同为两两配对判定，但配对条件是余数互补，用余数桶而非绝对值排序
659. 分割数组为连续子序列	中等	同样按值升序贪心消耗计数，只是消耗对象从 `2x` 变成连续的下一个数
1122. 数组的相对排序	简单	也用计数表驱动，但目的是按自定义次序重排而不是判定匹配可行性
621. 任务调度器	中等	频次统计后靠最大频次做贪心公式推导，不涉及元素间的一一配对
452. 用最少数量的箭引爆气球	中等	贪心正确性同样靠「最小者选择唯一」论证，但排序键是区间右端点
1. 两数之和	简单	哈希查找配对元素的入门形式，只需一对且无需考虑数量与顺序
870. 优势洗牌	中等	排序后贪心配对两个数组，考的是田忌赛马式的匹配策略