LeetCode 剑指 Offer 56 - I. 数组中数字出现的次数

约 10 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 百度 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 位运算
目录

题目描述

✅ 剑指 Offer 56 - I. 数组中数字出现的次数

image-20241107212019417

题意分析

一个整型数组里，恰好有两个数字只出现一次，其余所有数字都出现两次。要求把这两个只出现一次的数找出来，返回的顺序不限。

「其余全部出现两次」这个条件极强。它意味着如果把所有数字异或起来，成对出现的数字会两两抵消（$x \oplus x = 0$），只剩下那两个单独的数的异或值。这条性质是本题的起点，也是 136 题（只有一个数出现一次）的全部内容。

但本题有两个答案，异或的结果是 $a \oplus b$，是一个把两个答案糅在一起的数，无法直接拆开。如何从 $a \oplus b$ 里把 $a$ 和 $b$ 分离出来，才是这道题真正的考点。

题目的进阶要求写得很明确：时间复杂度 $O(n)$，空间复杂度 $O(1)$。这一条把哈希表统计（$O(n)$ 空间）和排序后扫描（$O(n\log n)$ 时间）两条直觉路线都堵死了，只剩位运算这一条路。看到「找出现次数异常的数」加上「常数空间」，几乎可以直接锁定异或。

数组长度上限是 10000，元素可为负数。负数意味着最高位是符号位，所有位运算都要在补码语义下考虑，不过下面用到的技巧对补码天然成立。

题目保证恰好有两个单独的数，所以不必处理「只有一个」或「一个都没有」的退化情形；也保证了 $a \neq b$，这一点后面会用到。

解法：异或分组

核心思路

先看能不能直接推广 136 的做法。全部异或得到 xor = a ^ b，然后呢？这个值同时包含了两个答案的信息，但没有任何办法从一个数里凭空还原出两个数。瓶颈在于两个答案被混在了同一个累加器里。

既然一个累加器装不下两个答案，那就用两个。问题变成：怎么把数组分成两组，使得 a 和 b 恰好落在不同组，而每一对相同的数字必须落在同一组？ 只要做到这两点，对每组分别做全体异或，成对的数字仍然自我抵消，每组就只剩一个单独的数。

分组的依据必须是由数值本身决定的（这样相同的数必然分到同一组），并且要能区分 a 和 b。回头看 xor = a ^ b：因为题目保证 a != b，所以 xor != 0，它至少有一个二进制位是 1。而异或的定义告诉我们，xor 中为 1 的每一位，都是 a 和 b 在该位上取值不同的位置。

于是任取 xor 的某一个为 1 的位作为分组依据即可：在这一位上是 0 的分到一组，是 1 的分到另一组。a 和 b 在这一位上必然一个 0 一个 1，被分开；而任何相同的两个数在所有位上都相同，必然同组。两个条件同时满足。

具体取哪一位无所谓，取最低位的 1 最省事，因为有现成的恒等式：lowbit = xor & -xor。原理是补码下 -xor 等于 ~xor + 1，取反会把最低位 1 右边的所有 0 变成 1、把最低位的 1 变成 0，再加 1 会让这串 1 全部进位回 0 并把最低位那个 0 变回 1，同时更高位保持为原值的按位取反；与原值相与后，只有最低位那个 1 存活。这个恒等式对负数同样成立。

第二趟遍历时用 (num & lowbit) == 0 分流，两个累加器 a、b 各自异或。维持的不变量是：每处理完一个元素，a 是「已扫描元素中在标记位为 0 的那些」的异或值，b 是标记位为 1 的那些的异或值。扫描结束时两组内的成对元素全部抵消，a 和 b 恰好就是两个只出现一次的数。

整个算法两趟线性扫描、只用三个整型变量，完美满足进阶要求，是面试官期待的标准答案。

解题步骤

  • 第一趟：把所有元素异或进 xor：累加器初值必须是 0，因为 0 是异或的单位元（$0 \oplus x = x$）。这一趟结束后 xor == a ^ b，所有成对元素已经抵消。
  • 计算 lowbit = xor & -xor：取出 xor 最低位的那个 1，作为分组标记。因为题目保证两个答案不同，xor 必然非零，lowbit 也必然非零，不会出现「所有元素分到同一组」的退化。用 xor & (-xor) 而不是循环找最低位，是常数级的写法。
  • 准备两个累加器 a = 0、b = 0：分别对应标记位为 0 和为 1 的那一组，初值同样取异或单位元。
  • 第二趟：按 (num & lowbit) == 0 分流并各自异或：注意 Java 里位运算符 & 的优先级低于 ==，外层括号不能省，写成 num & lowbit == 0 会被解析成 num & (lowbit == 0) 而编译失败或语义错乱；Go 的 & 优先级高于 ==，可以省括号，但加上更清晰。
  • 判断条件用 == 0 而不是 == 1：num & lowbit 的结果要么是 0、要么是 lowbit 本身（可能是 2、4、8……），只有当 lowbit 恰好是 1 时才等于 1。写成 == 1 在绝大多数用例上都会失效。
  • 返回 {a, b}：题目不限顺序，两个累加器直接装进数组即可，不需要排序或调整。

以 nums = [4, 1, 4, 6] 走一遍（两个单独的数是 1 和 6）。

第一趟：xor = 0 ^ 4 = 4（二进制 100）；^ 1 = 5（101）；^ 4 = 1（001，两个 4 抵消）；^ 6 = 7（111）。所以 xor = 7，正是 1 ^ 6。

取标记位：-7 在补码下是 ...11111001，7 & -7 = 001 即 lowbit = 1。这一位上 1 的二进制是 001（该位为 1），6 的二进制是 110（该位为 0），确实一个 0 一个 1，会被分开。

第二趟：元素 4（100），4 & 1 = 0，归入 a，a = 4。元素 1（001），1 & 1 = 1，归入 b，b = 1。元素 4，再次归入 a，a = 4 ^ 4 = 0——两个 4 在同一组里抵消掉了。元素 6（110），6 & 1 = 0，归入 a，a = 0 ^ 6 = 6。

返回 [6, 1]。两个只出现一次的数被正确分离，顺序不限所以合法。

这一趟清楚地展示了分组的两个必要条件如何同时被满足：两个 4 因为数值相同，在标记位上取值也相同，必然进同一组并抵消；而 1 和 6 因为在标记位上不同，被分进了不同的累加器，互不干扰。

再验证一个含负数的用例 nums = [-1, -1, 2, 3]：第一趟 xor = 2 ^ 3 = 1，lowbit = 1。第二趟中 -1 的补码末位是 1（...1111），两个 -1 都进 b 组并抵消；2（10）末位为 0 进 a 组，3（11）末位为 1 进 b 组。最终 a = 2、b = 3，正确——& 与 ^ 都是按补码逐位操作，负数无需任何特殊处理。

代码实现

class Solution {
    // 取 xor 的最低位 1 作为分组标记，将数组分成两组。
    public int[] singleNumbers(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }

        int lowbit = xor & -xor;
        int a = 0;
        int b = 0;

        for (int num : nums) {
            if ((num & lowbit) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return new int[]{a, b};
    }
}

func singleNumbers(nums []int) []int {
    // 取 xor 的最低位 1 作为分组标记，将数组分成两组。
    xor := 0
    for _, num := range nums {
        xor ^= num
    }

    lowbit := xor & -xor
    a, b := 0, 0

    for _, num := range nums {
        if num&lowbit == 0 {
            a ^= num
        } else {
            b ^= num
        }
    }

    return []int{a, b}
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组长度。两趟线性扫描，每个元素各做一次异或或一次按位与加一次异或；取 lowbit 是常数次运算。
  • 空间复杂度：$O(1)$，只用了 xor、lowbit、a、b 四个整型变量，与数组长度无关。这正是题目进阶要求的目标，也是异或解法相对哈希表统计的唯一但决定性的优势。

关键点总结

  • 异或的自反性 $x \oplus x = 0$ 和单位元 $0 \oplus x = x$，是所有「找出现次数异常的数」类问题的基石；看到「其余都出现两次」加上「常数空间」，直接往异或上想。
  • 一个累加器装不下两个答案时，思路应该是找一个由数值决定的分组依据，把两个答案分到不同的桶里。这个「分组后各自归约」的模式比记住本题结论更通用。
  • xor 中为 1 的位，正是两个答案取值不同的位——这句话是分组依据的全部理由，面试时必须能讲出来，而不是只说「取最低位 1」。
  • x & -x 取最低位的 1 是必背的位运算恒等式，且要能解释补码下的推导；它在树状数组、状态压缩枚举子集等场景里反复出现。
  • 判断分组要写 (num & lowbit) == 0，而不是 == 1——num & lowbit 的非零结果是 lowbit 本身而非 1。同时注意 Java 里 & 优先级低于 ==，括号不可省。
  • 所有位运算在补码下对负数天然成立，本题不需要为负数写任何特殊分支；能主动指出这一点会显得对底层表示有把握。

易错点总结

  • 判断写成 (num & lowbit) == 1：nums = [2,2,1,4] 时 xor = 5、lowbit = 1 恰好碰巧正确，但换成 nums = [4,4,2,6]，xor = 4、lowbit = 4，num & 4 的结果是 0 或 4，永远不等于 1，所有元素挤进同一组，返回 [0, 4] 之类的错误答案。
  • Java 里写成 num & lowbit == 0 不加括号：& 优先级低于 ==，表达式被解析成 num & (lowbit == 0)，直接编译报错；即使在 Go 里能通过，也应加括号避免误读。
  • lowbit 写成 xor & (xor - 1)：这是消去最低位 1 的写法，恰好取反了目标，nums = [1,2,1,3] 会得到 lowbit = 0，所有元素分到同一组，返回 [1, 0]。
  • 累加器初值不为 0：异或的单位元是 0，xor 初始化成 nums[0] 后又在循环里把 nums[0] 再异或一次，会把它凭空抵消掉，[1,2,1,3] 会返回错误结果。
  • 第二趟遍历时忘记重新扫描原数组，而是对 xor 做处理：xor 只是一个数，里面没有分组信息，任何试图从它单独还原两个答案的做法都不成立。
  • 只做一趟异或就返回 [xor, 0]：这是 136 题的答案，本题有两个单独的数，[1,2,1,3] 会返回 [1, 0] 而正确答案是 [2, 3]。
  • 用哈希表统计出现次数：结果正确但空间是 $O(n)$，不满足进阶要求，面试中会被要求改写。
  • 先排序再扫描相邻元素：时间退化到 $O(n \log n)$，且还要小心处理两个单独的数相邻、或位于数组首尾的边界，代码反而更长。
  • 误以为 lowbit 必须取最高位或某个固定位：任何一个为 1 的位都可用，硬写成 1 << 31 或固定 1，在 xor 该位为 0 时会把所有元素分到同一组。
  • 担心负数导致位运算出错而先取绝对值：Math.abs(Integer.MIN_VALUE) 仍是负数，且取绝对值会破坏成对元素的抵消关系，[-1,-1,2,3] 会返回错误答案。
  • 返回时强行调整两个数的顺序（如要求升序）：题目明确说明顺序不限，多余的排序不会出错但属于无谓开销；反过来，如果误以为必须按输入中出现的先后返回，也会白白增加复杂度。

相似题目

题目 难度 考察点
260. 只出现一次的数字 III 中等 与本题同题，可直接套用
136. 只出现一次的数字 简单 只有一个答案，全体异或即可，无需分组
137. 只出现一次的数字 II 中等 其余出现三次，异或无法抵消，需按位统计模 3 或用状态机
LCR 004. 只出现一次的数字 II 中等 与 137 同题
剑指 Offer 56 - II. 数组中数字出现的次数 II 中等 与 137 同题
268. 丢失的数字 简单 把下标与元素一起异或制造配对，缺失的那个自然剩下
剑指 Offer 53 - II. 0～n-1中缺失的数字 简单 与 268 同题，数组有序时还可用二分做到 $O(\log n)$
645. 错误的集合 简单 一个数重复一个数缺失，异或后同样要分组，是本题的直接变形
面试题 17.19. 消失的两个数字 困难 缺失两个数，需先用求和或异或构造出配对再按本题分组
389. 找不同 简单 把两个字符串的所有字符异或，多出的那个字符自然剩下
540. 有序数组中的单一元素 中等 数组有序，可利用配对下标的奇偶性二分到 $O(\log n)$，优于全体异或