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

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

题目描述

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

image-20241107212041526

题意分析

数组里除了一个数字只出现一次之外，其余每个数字都恰好出现三次，要求把那个只出现一次的数字找出来。

「恰好三次」是全题的支点。它保证了整个数组可以被划分成若干个完整的三元组，再加上一个孤零零的元素，不存在出现两次或四次这种残缺的情况。数组长度因此必然是 $3k + 1$。

隐含要求是线性时间和常数额外空间。用哈希表计一遍数当然能做，但那是 $O(n)$ 空间，会被追问；把数组排序再三个一组地看也能做，但那是 $O(n \log n)$ 时间。真正想考的是能不能只用固定几个变量走完一遍。

取值范围要留意。本题给出的数据都是正整数，但同一道题的 137 版本允许出现负数，而两者的解法完全一致——只要按补码的完整 32 位来处理，符号位不做任何特殊对待，两种数据都能被覆盖。

边界方面，数组长度最小为 $1$，此时唯一的元素就是答案，任何解法都必须能自然地返回它。

解法：逐位计数还原

核心思路

最省事的做法是开一张哈希表统计每个数出现的次数，再挑出计数为 $1$ 的那个。它是 $O(n)$ 时间，但空间也是 $O(n)$，达不到进阶要求。瓶颈在于它把「数」当成了不可拆分的整体来记账。

那么能不能沿用 136 的全体异或？不能。异或之所以能在「其余出现两次」时奏效，是因为相同的数两两异或会归零；而出现三次时，三个相同的数异或之后还剩一份自己，非但抵消不掉，反而把噪声混进了答案。异或本质上是模 $2$ 的加法，它天生只对偶数次有效。

关键的一跃是换掉计数的粒度：不去记「每个数出现了几次」，而去记「每个二进制位上出现了多少个 $1$」。把所有数按位对齐摞起来，看某一列。出现三次的那些数，在这一列上要么各贡献一个 $1$（合计 $3$ 个），要么各贡献 $0$ 个，无论哪种都是 $3$ 的倍数。也就是说，只要对这一列的 $1$ 求和再模 $3$，所有出现三次的数就被整整齐齐地约掉了，余下的完全来自那个唯一的数。

由此得到不变量：对每一个二进制位 b，把全体元素在该位上的 $1$ 的个数记作 $count_b$，则 $count_b \bmod 3$ 恰好等于答案在第 b 位上的取值。因为唯一的数在该位只能是 $0$ 或 $1$，所以这个余数也只可能是 $0$ 或 $1$，不会出现 $2$。

有了这条不变量，答案就可以逐位重建：余数为 $1$ 就把结果的第 b 位置 $1$，为 $0$ 就不动。位数固定为 $32$，与数组长度无关，所以整个过程是线性时间加常数空间。符号位（第 $31$ 位）不需要任何特殊处理——按补码的定义，把它置 $1$ 得到的正好是对应的负数。

这个思路还天然可以推广：把模 $3$ 换成模 k，就能解决「其余数字都出现 k 次」的一般情形，这正是它比各种异或技巧更值得掌握的原因。

解题步骤

  • 把结果 res 初始化为 $0$，接下来只会用按位或往里填 $1$，不会清位，所以从全零起步是安全的。
  • 外层循环枚举 bit 从 $0$ 到 $31$，覆盖完整的 32 位。上界必须是 $32$（即条件 bit < 32）而不是 $31$，否则最高位被漏掉；也不能写成 $33$，因为移位量超过 $31$ 在 Java 里会按模 $32$ 回绕。
  • 每进入一个新的位，都把 count 重新置为 $0$。计数必须按位隔离，count 的声明和清零都要落在外层循环体内部，否则各位的统计会串在一起。
  • 内层遍历数组，用 (num >> bit) & 1 取出该数在这一位上的值，为 $1$ 就让 count 加一。右移再与 $1$ 的写法把结果规范成了 $0$ 或 $1$，比直接与掩码更不容易出错。
  • 内层结束后判断 count % 3 != 0。用「不为零」而不是「等于一」只是习惯问题，两者在这里等价，因为余数不可能是 $2$；但用「等于二」就恒不成立了。
  • 条件成立时执行 res |= (1 << bit)，把结果的第 b 位置 $1$。用按位或而不是加法，是为了让这一句在任何执行次数下都幂等。
  • 32 位全部处理完后返回 res。Go 版本里要显式用 int32 承载结果，因为 Go 的 int 是 64 位，直接在它上面置第 $31$ 位得到的是正的 $2^{31}$ 而不是负数。

以 nums = [9, 1, 7, 9, 7, 9, 7] 走一遍：先写出各数的二进制，$9$ 是 1001，$1$ 是 0001，$7$ 是 0111。数组里 $9$ 出现三次、$7$ 出现三次、$1$ 出现一次。

bit = 0：$9$ 的第 $0$ 位是 $1$，三个 $9$ 贡献 $3$；$7$ 的第 $0$ 位是 $1$，三个 $7$ 贡献 $3$；$1$ 的第 $0$ 位是 $1$，贡献 $1$。count 为 $7$，$7 \bmod 3 = 1$ 不为零，执行 res |= 1，此时 res 为 $1$。

bit = 1：$9$ 的第 $1$ 位是 $0$，$1$ 的第 $1$ 位是 $0$，只有三个 $7$ 各贡献一个 $1$。count 为 $3$，$3 \bmod 3 = 0$，res 不变，仍为 $1$。

bit = 2：$9$ 的第 $2$ 位是 $0$，$1$ 的第 $2$ 位是 $0$，三个 $7$ 各贡献一个 $1$。count 为 $3$，余数为 $0$，res 仍为 $1$。

bit = 3：三个 $9$ 各贡献一个 $1$，$7$ 和 $1$ 在这一位都是 $0$。count 为 $3$，余数为 $0$，res 仍为 $1$。

bit 从 $4$ 到 $31$：所有数在这些位上都是 $0$，count 每轮都被清零后停在 $0$，余数为 $0$，res 不变。

循环结束返回 $1$，正是只出现一次的那个数。再用第一个样例 nums = [3, 4, 3, 3] 复核：第 $0$ 位上三个 $3$ 各贡献一个 $1$、$4$ 贡献 $0$，count 为 $3$ 余零；第 $1$ 位同样是三个 $3$ 贡献，count 为 $3$ 余零；第 $2$ 位只有 $4$ 贡献一个 $1$，count 为 $1$ 余一，置位得到 $4$；其余位全零。返回 $4$，与样例一致。

代码实现

class Solution {
    // 某一位计数对 3 取余不为 0，说明只出现一次的数字在这一位上是 1。
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int bit = 0; bit < 32; bit++) {
            int count = 0;
            for (int num : nums) {
                if (((num >> bit) & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 != 0) {
                res |= (1 << bit);
            }
        }
        return res;
    }
}

func singleNumber(nums []int) int {
    // 某一位计数对 3 取余不为 0，说明只出现一次的数字在这一位上是 1。
    var res int32
    for bit := 0; bit < 32; bit++ {
        count := 0
        for _, num := range nums {
            if (int32(num)>>bit)&1 == 1 {
                count++
            }
        }
        if count%3 != 0 {
            res |= int32(1) << bit
        }
    }

    return int(res)
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 是数组长度。外层固定跑 $32$ 轮，内层每轮完整扫一遍数组，总操作数是 $32n$；位数是与输入规模无关的常数，所以整体是线性的。
  • 空间复杂度：$O(1)$，只用了 res、count、bit 这几个整型变量。计数是按位就地累加再丢弃的，不需要为 $32$ 个位同时保留计数，更不需要按数值建表。

关键点总结

  • 当整体层面的抵消技巧失效时，试着把数据拆到更细的粒度上重新记账。本题把「按数计数」换成「按位计数」，就把一个需要哈希表的问题压成了常数空间。
  • 异或只是模 $2$ 加法的特例，它天生只能消掉偶数次重复。看到「出现三次」「出现 k 次」时要立刻意识到异或不适用，转而考虑模 k 的按位求和。
  • 这个解法的推广性是它最大的价值：把 $3$ 换成任意 k，代码一个字都不用改结构。面试里能顺手说出这一点，比写出更炫的状态机写法更有说服力。
  • 处理带符号整数的位运算时，把符号位当成普通的第 $31$ 位一起统计即可，补码的定义会保证重建结果正确；反而是「为负数单独加一段逻辑」容易出错。
  • 面试视角：面试官大概率会先让你说哈希表解法，再问 $O(1)$ 空间。逐位计数是最容易讲清楚也最不容易写错的答案，应当作为首选给出，而不是一上来就默写 ones、twos 那套状态机。
  • 面试视角：若被追问还有没有更快的写法，可以提及用两个变量模拟三进制计数器的位运算解法，它把 $32$ 轮外层循环压成一次遍历。但要诚实说明它的正确性依赖对状态转移的逐位验证，可读性远不如逐位计数。

易错点总结

  • 错误写法：套用 136 的「全体异或」→ 三个相同的数异或后仍剩下一份自己。以 nums = [3, 4, 3, 3] 为例，$3 \oplus 4 = 7$，$7 \oplus 3 = 4$，$4 \oplus 3 = 7$，最终得到 $7$，而正确答案是 $4$。
  • 错误写法：把 count 声明在位循环之外且不清零 → 各位的计数首尾相接地累积。以 nums = [9, 1, 7, 9, 7, 9, 7] 为例，count 依次变成 $7$、$10$、$13$、$16$ 后不再增长，模 $3$ 全是 $1$，$32$ 个位被全部置 $1$，返回 $-1$ 而不是 $1$。
  • 错误写法：位循环上界写成 bit < 31 → 第 $31$ 位从不参与统计。在允许负数的同题版本上，答案为负时符号位丢失，返回的是一个和真实值相差 $2^{31}$ 的正数。
  • 错误写法：位循环上界写成 bit <= 32 → Java 的移位量会按 $32$ 取模，1 << 32 等于 $1$，最低位可能被再置一次，答案被平白加上 $1$。
  • 错误写法：判断写成 count % 3 == 2 → 余数只可能是 $0$ 或 $1$（唯一数的某位不是 $0$ 就是 $1$），这个条件恒不成立，函数永远返回 $0$。
  • 错误写法：在 Go 里直接用 64 位的 int 承载结果并置第 $31$ 位 → 得到的是正的 $2^{31}$，而不是 32 位补码下对应的负数；必须用 int32 参与移位和或运算，最后再转回 int。
  • 错误写法：改用哈希表统计每个数的出现次数 → 结果正确但空间是 $O(n)$，本题的进阶要求正是常数空间，面试中给出这一版会被立刻要求重写。
  • 错误写法：先排序再每三个一组比较 → 时间退化到 $O(n \log n)$，而且唯一的数落在数组末尾时最后一组不足三个，需要额外的越界处理，稍不留神就漏掉这种情况。
  • 错误写法：用「去重后求和乘三再减去原和，最后除以二」的公式 → 公式本身成立，但去重必须借助集合，空间回到 $O(n)$；而且三倍求和在元素接近整型上界时会溢出，得不到正确的差值。

相似题目

题目 难度 考察点
137. 只出现一次的数字 II 中等 与本题同题但明确允许负数，可用来检验符号位是否被正确统计
136. 只出现一次的数字 简单 其余出现两次，全体异或即可，是理解「异或只消偶数次」的对照组
260. 只出现一次的数字 III 中等 有两个唯一数，需先用最低位的 $1$ 把数组分成两组再分别异或
剑指 Offer 56 - I. 数组中数字出现的次数 中等 与 260 同题，考察如何构造分组掩码而不是如何按位计数
LCR 004. 只出现一次的数字 II 中等 与本题同题的新版编号，适合直接对照逐位计数与状态机两种写法
191. 位1的个数 简单 单个数的按位统计，是本题内层循环的最小单元，可练习无符号右移
LCR 003. 比特位计数 简单 批量求各数的二进制中 $1$ 的个数，用递推代替逐位扫描