LeetCode 136 - 只出现一次的数字（Single Number）

问题描述

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

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1：

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

示例 2：

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

约束条件：

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• 除了某个元素只出现一次外，其余每个元素均出现两次

解题思路

这道题可以有多种解法，我们将介绍三种不同的解决方案，从简单到高级，最后重点讲解使用异或运算的解法。

方法一：哈希表计数法

核心思想：使用哈希表记录每个数字出现的次数，然后找出只出现一次的数字。

实现步骤

1. 创建一个哈希表 map，用于存储数组中每个元素出现的次数
2. 遍历数组，对每个元素进行计数
3. 再次遍历哈希表，找出出现次数为 1 的元素

方法二：排序法

核心思想：先对数组进行排序，然后比较相邻元素，找出只出现一次的数字。

实现步骤

1. 对数组进行排序
2. 从头到尾遍历排序后的数组
3. 由于除了一个元素外，其他元素都出现两次，所以相同的元素必然相邻
4. 比较相邻元素，找出不成对的元素

方法三：异或运算法（最优解）

核心思想：利用异或运算的特性，对数组中所有元素进行异或运算，最终结果就是只出现一次的元素。

异或运算的关键特性：

• 任何数字与 0 异或等于它自己：a ⊕ 0 = a
• 任何数字与自己异或等于 0：a ⊕ a = 0
• 异或运算满足交换律和结合律：a ⊕ b = b ⊕ a 和 (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

实现步骤

1. 初始化结果变量 res = 0
2. 遍历数组中的每个元素，将其与 res 进行异或运算
3. 最终 res 的值就是只出现一次的元素

实现细节

让我们更详细地解释这三种方法的具体实现：

哈希表计数法详解

这是最直观的解法。我们使用一个哈希表来记录每个元素出现的次数：

1. 遍历数组，将每个元素作为键，出现次数作为值存入哈希表
2. 再次遍历哈希表，找到值为 1 的键，即为答案

这种方法的优点是直观易懂，适合初学者理解。缺点是需要额外的 O(n) 空间复杂度，不满足题目要求的"不使用额外空间"。

排序法详解

排序后，相同的元素会相邻，我们可以利用这个特性：

1. 对数组进行排序
2. 从头到尾遍历排序后的数组，每次跳过两个元素
3. 如果相邻元素不相等，那么这就是我们要找的元素

但这种方法的时间复杂度为 O(n log n)，不满足要求的线性时间复杂度。

异或运算法详解（重点）

为什么异或运算可以解决这个问题？

让我们先简单介绍异或运算：

异或运算（XOR）是一种位运算，用符号 ⊕ 或 ^ 表示。它有一个很重要的特性：当两个相同的数进行异或时，结果为 0；而任何数与 0 异或，结果仍为它本身。

用真值表表示：

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

生活中的例子：可以把异或运算想象成"开关"，每次操作会改变开关状态。如果开关初始为关闭（0），第一次按下会打开（1），第二次再按则会关闭（0）。这就像异或的特性：任何数字出现偶数次会抵消为 0。

重要特性总结：

1. a ⊕ 0 = a：任何数与 0 异或仍为它本身
2. a ⊕ a = 0：任何数与自身异或等于 0
3. a ⊕ b ⊕ a = b：由上面两条推导出的性质

为什么这个问题可以用异或解决？

在我们的问题中：

• 数组中有一个元素出现一次，其余元素都出现两次
• 将所有元素进行异或运算，出现两次的元素会互相抵消（结果为 0）
• 0 与只出现一次的元素异或，结果就是该元素

图解过程：

以输入 [4,1,2,1,2] 为例：

1. 初始 res = 0
2. res = 0 ⊕ 4 = 4
3. res = 4 ⊕ 1 = 5
4. res = 5 ⊕ 2 = 7
5. res = 7 ⊕ 1 = 6 (因为 1 出现两次，所以 1 ⊕ 1 = 0，这一步相当于 7 ⊕ 0 = 7）
6. res = 6 ⊕ 2 = 4 (因为 2 出现两次，所以 2 ⊕ 2 = 0，这一步相当于 6 ⊕ 0 = 6）

最终 res = 4，这就是只出现一次的元素。

另一种理解方式：

将上面的步骤重新组织，利用异或的交换律和结合律：

res = 0 ⊕ 4 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2
    = 0 ⊕ 4 ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2)
    = 0 ⊕ 4 ⊕ 0 ⊕ 0
    = 4

这样更直观地看出，相同的元素通过异或运算会抵消为 0，最终只留下出现一次的元素。

代码实现

下面是三种解法的 Go 语言实现：

方法一：哈希表计数法

func singleNumber(nums []int) int {
    // 创建哈希表
    countMap := make(map[int]int)
    
    // 统计每个元素出现的次数
    for _, num := range nums {
        countMap[num]++
    }
    
    // 找出只出现一次的元素
    for num, count := range countMap {
        if count == 1 {
            return num
        }
    }
    
    return 0 // 这行理论上不会执行，因为题目保证有一个元素仅出现一次
}

方法二：排序法

func singleNumber(nums []int) int {
    // 对数组进行排序
    sort.Ints(nums)
    
    // 特殊情况处理：如果数组长度为1，直接返回
    if len(nums) == 1 {
        return nums[0]
    }
    
    // 处理第一个元素可能是单个的情况
    if nums[0] != nums[1] {
        return nums[0]
    }
    
    // 处理中间元素
    for i := 1; i < len(nums)-1; i += 2 {
        if nums[i] != nums[i+1] && i+1 < len(nums) {
            return nums[i+1]
        }
        if nums[i] != nums[i-1] {
            return nums[i]
        }
    }
    
    // 处理最后一个元素可能是单个的情况
    return nums[len(nums)-1]
}

方法三：异或运算法（最优解）

func singleNumber(nums []int) int {
    res := 0
    for _, num := range nums {
        res ^= num
    }
    
    return res
}

这就是题目中展示的解法，简洁而高效。

方法比较

方面	方法一：哈希表计数法	方法二：排序法	方法三：异或运算法
时间复杂度	O(n)	O(n log n)	O(n)
空间复杂度	O(n)	O(1) 或 O(log n)	O(1)
优点	直观易懂	思路简单	最优解，符合题目所有要求
缺点	需要额外空间	时间复杂度较高	需要理解异或运算原理
适用场景	通用场景，元素出现任意次	通用场景，元素出现任意次	特定场景，元素出现偶数次
推荐度	★★★☆☆	★★☆☆☆	★★★★★

复杂度分析

方法一：哈希表计数法

• 时间复杂度：O(n)，需要遍历数组一次，然后遍历哈希表一次
• 空间复杂度：O(n)，需要额外的哈希表存储每个元素的出现次数

方法二：排序法

• 时间复杂度：O(n log n)，排序的时间复杂度
• 空间复杂度：O(1) 或 O(log n)，取决于排序算法的实现

方法三：异或运算法

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(1)，只需要一个变量存储结果

关键收获

1. 异或运算的独特作用：异或运算在处理"出现偶数次"的元素时具有特殊优势，可以实现"自动抵消"的效果。

2. 限制条件的重要性：这种解法之所以有效，是因为题目保证了除了一个元素外，其他元素都出现两次（偶数次）。如果元素出现奇数次，异或运算就不适用了。

3. 空间复杂度优化：有时候，利用问题的特殊性质可以大幅降低空间复杂度，异或运算法就是一个很好的例子。

4. 位运算的强大：位运算通常可以带来更高效的解法，特别是在处理数字相关问题时。

5. 适用场景的拓展：异或运算法不仅适用于元素出现两次的情况，只要其他元素都出现偶数次，这种方法都是有效的。

6. 特殊情况的处理：需要注意的是，这种方法只能找出唯一一个出现奇数次的元素。如果有多个元素出现奇数次，就需要其他方法。

总结：异或运算法提供了一种巧妙的方式来解决"只出现一次的数字"问题，它利用位操作的特性，实现了线性时间复杂度和常数空间复杂度，是一种非常优雅的解决方案。