只出现一次的数字 II
📌 定义
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。
要求：时间复杂度 O(n)，空间复杂度 O(1)
示例:
输入: [2,2,3,2]
输出: 3
输入: [0,1,0,1,0,1,99]
输出: 99
核心思路
由于每个数字出现3次，不能直接使用异或。需要使用位计数法：
核心原理：
- 统计所有数字每一位上 1 的总数
- 如果某一位上 1 的总数不是 3 的倍数，说明只出现一次的数字在该位上是 1
- 将所有这样的位组合起来，就是答案
示例: [2, 2, 3, 2]
二进制表示:
2: 010
2: 010
3: 011
2: 010
统计每一位的1:
第0位: 1 (3的倍数) + 1 = 1 → 1 % 3 = 1 ✓
第1位: 3 (3的倍数) + 1 = 4 → 4 % 3 = 1 ✓
第2位: 0
结果: 011 (二进制) = 3
复杂度分析
| 指标 | 哈希表 | 位计数 | 状态机 |
|---|---|---|---|
| 时间复杂度 | O(n) | O(n) | O(n) |
| 空间复杂度 | O(n) | O(1) | O(1) |
| 实现难度 | 简单 | 中等 | 困难 |
Go 代码
Go 实现
package main
import "fmt"
// 方法1: 位计数法
func singleNumber(nums []int) int {
result := 0
for i := 0; i < 32; i++ {
count := 0
// 统计第i位上1的个数
for _, num := range nums {
count += (num >> i) & 1
}
// 如果不是3的倍数
if count%3 != 0 {
result |= (1 << i)
}
}
return result
}
// 方法2: 状态机法
func singleNumberStateMachine(nums []int) int {
ones, twos := 0, 0
for _, num := range nums {
twos |= ones & num
ones ^= num
threes := ones & twos
ones &= ^threes
twos &= ^threes
}
return ones
}
func main() {
testCases := [][]int{
{2, 2, 3, 2},
{0, 1, 0, 1, 0, 1, 99},
}
for _, nums := range testCases {
result := singleNumber(nums)
fmt.Printf("%v 中只出现一次的数字: %d\n", nums, result)
}
}思路展开
方法1：位计数法详解
数组: [2, 2, 3, 2]
二进制表示:
2: 010
2: 010
3: 011
2: 010
统计每一位:
第0位: 0+0+1+0 = 1 → 1 % 3 = 1 ✓
第1位: 1+1+1+1 = 4 → 4 % 3 = 1 ✓
第2位: 0+0+0+0 = 0 → 0 % 3 = 0
构建结果:
第0位为1: result |= (1 << 0) → result = 001
第1位为1: result |= (1 << 1) → result = 011
最终结果: 011 (二进制) = 3 (十进制)
方法2：状态机法详解
状态转换表:
当前状态 | 输入 | 下一状态
(twos,ones) | num | (twos',ones')
---------------------------------
(0, 0) | 1 | (0, 1) 出现1次
(0, 1) | 1 | (1, 0) 出现2次
(1, 0) | 1 | (0, 0) 出现3次（清零）
处理 [2, 2, 3, 2]:
初始: ones=0, twos=0
处理 2 (010):
twos = 0 | (0 & 2) = 0
ones = 0 ^ 2 = 2
threes = 2 & 0 = 0
状态: ones=2, twos=0
处理 2 (010):
twos = 0 | (2 & 2) = 2
ones = 2 ^ 2 = 0
threes = 0 & 2 = 0
状态: ones=0, twos=2
处理 3 (011):
twos = 2 | (0 & 3) = 2
ones = 0 ^ 3 = 3
threes = 3 & 2 = 2
ones = 3 & ~2 = 1
twos = 2 & ~2 = 0
状态: ones=3, twos=2
处理 2 (010):
twos = 2 | (3 & 2) = 2
ones = 3 ^ 2 = 1
threes = 1 & 2 = 0
状态: ones=3, twos=2
最终结果: ones = 3
经典题目
LeetCode 问题
- 只出现一次的数字 I - LeetCode 136（每个元素出现2次）
- 只出现一次的数字 II - LeetCode 137
- 只出现一次的数字 III - LeetCode 260（有2个元素只出现一次）
扩展问题
- 只出现一次的数字 IV（每个元素出现 k 次，一个出现 1 次）
- 数组中出现次数超过一半的数字
⚖️ 优缺点
优点
- ✅ 空间复杂度 O(1)：不需要额外存储
- ✅ 适用范围广：可推广到出现 k 次的情况
- ✅ 处理负数：位计数法可以正确处理负数
缺点
- ❌ 实现复杂：比简单异或复杂得多
- ❌ 常数因子较大：需要遍历32位
- ❌ 不够直观：状态机法需要数字电路知识
🎨 应用场景
💡 优化技巧
相关主题
- 只出现一次的数字 I - 出现2次的简单版本
- 只出现一次的数字 III - 两个单独元素
- 位运算 - 返回位运算总览
- 数组 - 数组相关算法