只出现一次的数字 I
📌 定义
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
要求：时间复杂度 O(n)，空间复杂度 O(1)
示例:
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
核心思路
利用异或运算的性质：
- 任何数和 0 异或，结果仍是原数：
a ⊕ 0 = a - 任何数和自身异或，结果为 0：
a ⊕ a = 0 - 异或运算满足交换律和结合律：
a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b
因此，将所有数字进行异或运算，成对的数字会相互抵消变成 0，最后剩下的就是只出现一次的数字。
过程演示:
[4, 1, 2, 1, 2]
4 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2
= 4 ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2)
= 4 ⊕ 0 ⊕ 0
= 4
复杂度分析
| 指标 | 哈希表 | 位运算（异或） |
|---|---|---|
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(n) | O(1) |
| 实现难度 | 简单 | 简单 |
Go 代码
Go 实现
package main
import "fmt"
func singleNumber(nums []int) int {
result := 0
for _, num := range nums {
result ^= num
}
return result
}
// 递归实现
func singleNumberRecursive(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
return nums[0] ^ singleNumberRecursive(nums[1:])
}
func main() {
testCases := [][]int{
{2, 2, 1},
{4, 1, 2, 1, 2},
{1},
}
for _, nums := range testCases {
result := singleNumber(nums)
fmt.Printf("%v 中只出现一次的数字: %d\n", nums, result)
}
}思路展开
异或运算过程
数组: [4, 1, 2, 1, 2]
步骤 1: result = 0
步骤 2: result = 0 ⊕ 4 = 4
二进制: 000 ⊕ 100 = 100
步骤 3: result = 4 ⊕ 1 = 5
二进制: 100 ⊕ 001 = 101
步骤 4: result = 5 ⊕ 2 = 7
二进制: 101 ⊕ 010 = 111
步骤 5: result = 7 ⊕ 1 = 6
二进制: 111 ⊕ 001 = 110
步骤 6: result = 6 ⊕ 2 = 4
二进制: 110 ⊕ 010 = 100
最终结果: 4
数学证明
设数组为 [a, a, b, b, c]，其中 c 只出现一次
异或所有元素:
a ⊕ a ⊕ b ⊕ b ⊕ c
根据交换律和结合律:
= (a ⊕ a) ⊕ (b ⊕ b) ⊕ c
根据 x ⊕ x = 0:
= 0 ⊕ 0 ⊕ c
根据 x ⊕ 0 = x:
= c
证毕 ✓
经典题目
LeetCode 问题
- 只出现一次的数字 - LeetCode 136
- 只出现一次的数字 II - LeetCode 137（每个元素出现3次）
- 只出现一次的数字 III - LeetCode 260（有2个元素只出现一次）
变体问题
- 只出现一次的数字 IV（每个元素出现 k 次，一个出现 1 次）
- 数组中重复的数字
⚖️ 优缺点
优点
- ✅ 空间效率极高：O(1) 空间复杂度
- ✅ 时间效率高：O(n) 线性时间
- ✅ 实现简单：只需一行核心代码
- ✅ 无需额外存储：不需要哈希表或数组
缺点
- ❌ 限制条件严格：只适用于”其他数字出现偶数次”的场景
- ❌ 不适用于出现奇数次：如果其他数字出现3次，需要其他方法
🎨 应用场景
- 成对抵消：当数据天然以成对形式出现时，用异或消除重复值。
- 状态切换：异或可以表示“开关翻转”，常用于位掩码状态更新。
- 校验与差异定位：两组元素除顺序外完全相同，异或结果可以定位只出现一次的差异。
💡 扩展：多种解法对比
| 方法 | 时间复杂度 | 额外空间 | 适用条件 |
|---|---|---|---|
| 异或 | O(n) | O(1) | 其他元素恰好出现两次 |
| 哈希表计数 | O(n) | O(n) | 出现次数规则更复杂 |
| 排序后扫描 | O(n log n) | 视排序实现而定 | 允许改变数组顺序 |
如果题目把“出现两次”改成“出现三次”，异或无法直接抵消，需要按位统计后对次数取模，见 只出现一次的数字 II。
相关主题
- 只出现一次的数字 II - 出现3次的变体
- 只出现一次的数字 III - 两个单独元素
- 位运算 - 返回位运算总览
- 数组 - 数组相关算法