LeetCode 954. 二倍数对数组

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 哈希表 排序 贪心

题目描述

✅ 954. 二倍数对数组

image-20260929105349869

题意分析

判断能否把偶数个元素全部分成若干对，每对都满足第二个数等于第一个数的两倍。每个元素只能用一次；负数、0 和重复值都可能出现。只需判断是否存在这样的分组，不必输出具体排列。

解法：排序 + 贪心

核心思路

[!blue]

先用频次表记录每个值还剩多少个，再把不同的值按绝对值从小到大处理。考虑当前剩余的非零值 x：如果它作为某对的两倍数，就需要一个绝对值更小的 x / 2；但所有更小绝对值的元素已经处理完，所以剩下的 x 只能作为原数，与 2x 配对。

设 x 当前还剩 cnt 个，那么至少要有 cnt 个未使用的 2x。不足就无解；足够就从 2x 的频次中扣去 cnt，再把 x 清零。这个选择是剩余元素中被迫做出的配对，不会排除其他可行方案。每次都维持频次代表“尚未使用元素”的含义，全部处理完成即配对成功。

绝对值顺序同时覆盖正负数：非零原数的绝对值一定小于它的两倍数。若直接按普通数值升序处理，负数的两倍数会先被处理，顺序反而颠倒。绝对值相同的正负数互不配对，各自需要同符号的两倍数，所以它们之间的处理顺序无关紧要。

0 是唯一的特殊情况，因为它的两倍仍是自己，不能按两个不同键扣减。每对必须消耗两个 0，因此零的频次为偶数才合法；检查后直接清零。已经被更小绝对值元素用完的值，其剩余频次为 0，跳过即可。

解题步骤

  1. 统计各值频次，将所有不同值作为待处理键。
  2. 按绝对值升序排列这些键。
  3. 读取当前值的剩余频次，为 0 则跳过；当前值为 0 时检查频次是否为偶数。
  4. 对非零值，若两倍数剩余频次不足，返回 false；否则批量扣除配对所需数量，并清空当前值。
  5. 所有键处理完后返回 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;
    }
}

import "sort"

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+k\log(k+1))$，k 为不同值数量。
  • 空间复杂度：$O(k+1)$，k 为不同值数量；排序的是键，输入数组不改。

关键点总结

[!green]

  • 按绝对值处理，使当前剩余非零元素无法再作为某个未处理数的两倍数，配对方向因此确定。
  • 频次始终记录剩余数量，重复值按数量一起消耗，而不是只判断键是否存在。
  • 零的配对需要两个相同元素，单独检查奇偶性。

易错点总结

[!yellow]

  • 按普通升序找两倍数，会在负数部分错误地先处理绝对值更大的元素。
  • 使用集合或只检查 2x 是否存在，无法保证有足够的副本完成全部配对。
  • 处理当前键时必须读取剩余频次，不能沿用它在之前配对前的原始数量。
  • 非零值配对后，既要扣减两倍数的供应量，也要清空已经使用的当前值。
  • 将 0 当作一般非零值处理，可能错误接受奇数个 0。

相似题目

题目 难度 关联与区别
2007. 从双倍数组中还原原数组 中等 同样按频次配对x与2x，原题恢复非负原数组，本题允许负值并只判断能否全部配对。
1679. K 和数对的最大数目 中等 同样配对后消耗频次，但本题互补关系是倍数，需要按绝对值顺序先处理小值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/13201592
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！