只出现一次的数字 III
📌 定义
给定一个整数数组，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出这两个只出现一次的元素。
要求：时间复杂度 O(n)，空间复杂度 O(1)
示例:
输入: [1,2,1,3,2,5]
输出: [3,5]
输入: [-1,0]
输出: [-1,0]
输入: [0,1]
输出: [1,0]
核心思路
这是 只出现一次的数字 I 的升级版，有两个单独元素。
解决思路：
- 第一步：对所有数字异或，得到两个单独数字的异或结果
- 第二步：找到异或结果中任意一个为 1 的位（说明两个数在该位不同）
- 第三步：根据该位是否为 1，将所有数字分成两组
- 第四步：对两组分别异或，得到两个单独的数字
示例: [1, 2, 1, 3, 2, 5]
二进制:
1: 001
2: 010
1: 001
3: 011
2: 010
5: 101
步骤1: 全部异或
xor = 1 ⊕ 2 ⊕ 1 ⊕ 3 ⊕ 2 ⊕ 5 = 3 ⊕ 5 = 011 ⊕ 101 = 110
步骤2: 找到最右边的1（第1位）
rightmost_bit = 110 & -110 = 010
步骤3: 按第1位分组
组1（第1位=1）: 2, 3, 2 → 异或 = 3
组2（第1位=0）: 1, 1, 5 → 异或 = 5
结果: [3, 5]
复杂度分析
| 指标 | 哈希表 | 位运算分组 |
|---|---|---|
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(n) | O(1) |
| 实现难度 | 简单 | 中等 |
Go 代码
Go 实现
package main
import "fmt"
func singleNumber(nums []int) []int {
// 步骤1: 获取两个单独数字的异或结果
xor := 0
for _, num := range nums {
xor ^= num
}
// 步骤2: 找到最右边的1
rightmostBit := xor & -xor
// 步骤3: 分组并异或
num1, num2 := 0, 0
for _, num := range nums {
if num&rightmostBit != 0 {
num1 ^= num
} else {
num2 ^= num
}
}
return []int{num1, num2}
}
// 使用位操作找到第k个为1的位
func singleNumberKthBit(nums []int, k int) []int {
xor := 0
for _, num := range nums {
xor ^= num
}
// 找到第k个为1的位
bit := 1
for i := 0; i < k; i++ {
for xor&bit == 0 {
bit <<= 1
}
if i < k-1 {
bit <<= 1
}
}
num1, num2 := 0, 0
for _, num := range nums {
if num&bit != 0 {
num1 ^= num
} else {
num2 ^= num
}
}
return []int{num1, num2}
}
func main() {
testCases := [][]int{
{1, 2, 1, 3, 2, 5},
{-1, 0},
{0, 1},
}
for _, nums := range testCases {
result := singleNumber(nums)
fmt.Printf("%v 中只出现一次的数字: %v\n", nums, result)
}
}思路展开
详细步骤演示
数组: [1, 2, 1, 3, 2, 5]
=== 步骤1: 全部异或 ===
xor = 1 ⊕ 2 ⊕ 1 ⊕ 3 ⊕ 2 ⊕ 5
= (1 ⊕ 1) ⊕ (2 ⊕ 2) ⊕ 3 ⊕ 5
= 0 ⊕ 0 ⊕ 3 ⊕ 5
= 3 ⊕ 5
= 011 ⊕ 101
= 110 (十进制 6)
=== 步骤2: 找最右边的1 ===
xor = 110
-xor = ...11010 (补码)
xor & -xor = 110 & ...11010 = 010 (十进制 2)
解释:
110 (6的二进制)
& ...11010 (-6的补码)
= 010 (第1位为1)
=== 步骤3: 按第1位分组 ===
第1位为1的数字:
2 (010) ✓
3 (011) ✓
2 (010) ✓
异或: 2 ⊕ 3 ⊕ 2 = 3
第1位为0的数字:
1 (001)
1 (001)
5 (101)
异或: 1 ⊕ 1 ⊕ 5 = 5
=== 结果 ===
[3, 5]
为什么 x & -x 能获取最右边的1？
示例: x = 6 (110)
原码: 00000110
反码: 11111001 (取反)
补码: 11111010 (反码+1，即-x)
x & -x:
00000110
& 11111010
-----------
00000010 ← 只保留了最右边的1
数学原理:
-x = ~x + 1
当 x = ...abc100...0 (最右边的1后面都是0)
~x = ...~a~b~c011...1
-x = ...~a~b~c100...0
x & -x = ...000100...0 (只保留最右边的1)
分组原理
设两个单独的数字为 a 和 b
xor = a ⊕ b
如果 xor 的第i位为1，说明:
- a 的第i位和 b 的第i位不同
- 一个是0，一个是1
根据第i位分组:
- 组1: 所有第i位为1的数字（包含 a 或 b 其中之一）
- 组2: 所有第i位为0的数字（包含 b 或 a 其中之一）
每组内部:
- 其他数字都成对出现，异或后为0
- 只剩下单独的数字
经典题目
LeetCode 问题
- 只出现一次的数字 I - LeetCode 136（一个元素只出现一次）
- 只出现一次的数字 II - LeetCode 137（每个元素出现3次）
- 只出现一次的数字 III - LeetCode 260
扩展问题
- 数组中出现次数超过一半的数字
- 数组中唯一的重复元素
⚖️ 优缺点
优点
- ✅ 空间复杂度 O(1)：不需要额外存储
- ✅ 时间复杂度 O(n)：只需遍历两次数组
- ✅ 巧妙利用异或性质：优雅的位运算技巧
缺点
- ❌ 理解难度高：需要深入理解位运算
- ❌ 限制条件严格：只适用于其他数字成对出现的场景
- ❌ 调试困难：位运算不够直观
🎨 应用场景
💡 优化技巧
相关主题
- 只出现一次的数字 I - 基础版本
- 只出现一次的数字 II - 出现3次的变体
- 位运算 - 返回位运算总览
- 数组 - 数组相关算法