我来给你讲解 LeetCode 第 136 题「只出现一次的数字」。

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

要求：

• 线性时间复杂度 O(n)
• 不使用额外空间（O(1) 空间复杂度）

示例：

输入: [2,2,1]
输出: 1

输入: [4,1,2,1,2]
输出: 4

解题思路分析

第一步：理解问题本质

我们先分析题目的关键信息：

• 数组中只有一个元素出现一次
• 其他所有元素都出现两次
• 需要高效解决（O(n)时间，O(1)空间）

第二步：思考基础解法

如果没有空间限制，我们可以用哈希表：

• 遍历数组，统计每个数字出现的次数
• 再遍历哈希表，找到出现一次的数字
• 时间复杂度 O(n)，但空间复杂度 O(n)，不符合要求

第三步：寻找更优解法

我们需要找到一种能在 O(1) 空间内解决问题的方法。这里的关键洞察是：异或运算（XOR）。

异或运算的特性：

1. a ^ 0 = a（任何数与0异或等于自身）
2. a ^ a = 0（任何数与自身异或等于0）
3. a ^ b ^ a = b（异或满足交换律和结合律）

第四步：应用异或运算

利用异或特性，我们可以这样思考：

• 出现两次的数字会相互抵消（a ^ a = 0）
• 出现一次的数字会保留下来（a ^ 0 = a）

具体过程：
对于数组 [4, 1, 2, 1, 2]

初始值: result = 0
0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4  ← 最终结果

验证计算过程：

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)  // 交换结合
= 4 ^ 0 ^ 0
= 4

第五步：算法步骤

1. 初始化结果变量 result = 0
2. 遍历数组中的每个数字 num
3. 对每个数字执行异或操作：result = result ^ num
4. 遍历完成后，result 就是只出现一次的数字

第六步：代码实现（伪代码）

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

第七步：复杂度分析

• 时间复杂度：O(n)，只需要遍历一次数组
• 空间复杂度：O(1)，只使用了一个额外变量

第八步：验证示例

示例1：[2, 2, 1]

0 ^ 2 = 2
2 ^ 2 = 0
0 ^ 1 = 1  ✓

示例2：[4, 1, 2, 1, 2]

0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4  ✓

关键总结

这道题的核心是利用异或运算的消去特性：

• 相同的数字异或会相互抵消为0
• 最终只剩下出现一次的数字
• 这种方法既高效又节省空间

这种思路在解决"找出唯一不同元素"类问题时非常有用，是位运算的经典应用场景。