在Python中,singleNumber 通常指的是一个经典的算法问题：在一个非空整数数组中，除了一个元素只出现一次外，其他每个元素均出现两次，找出那个只出现一次的元素。
（图片来源网络，侵删）
这个问题有多种高效的解法,下面我将为你详细介绍最常用和最高效的几种方法。
使用异或 (XOR) 运算 (最优解)
这是解决此问题的最佳方法,因为它满足所有要求：时间复杂度为 O(n)，空间复杂度为 O(1)，并且代码非常简洁。
原理
异或运算 (^) 有以下几个关键特性：
- 任何数和 0 异或，结果仍然是原来的数：
a ^ 0 = a - 任何数和其自身异或，结果是 0：
a ^ a = 0 - 异或运算满足交换律和结合律：
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
根据这些特性,我们可以将数组中所有的数字进行异或运算，成对出现的数字会相互抵消（结果为0），最终剩下的就是那个只出现一次的数字。
（图片来源网络，侵删）
代码实现
def singleNumber(nums):
"""
使用异或运算找到只出现一次的数字。
参数:
nums (list[int]): 一个整数列表，其中只有一个元素出现一次，其余都出现两次。
返回:
int: 那个只出现一次的数字。
"""
result = 0
for num in nums:
result ^= num
return result
# --- 示例 ---
nums1 = [4, 1, 2, 1, 2]
print(f"数组 {nums1} 中只出现一次的数字是: {singleNumber(nums1)}") # 输出: 4
nums2 = [2, 2, 1]
print(f"数组 {nums2} 中只出现一次的数字是: {singleNumber(nums2)}") # 输出: 1
复杂度分析
- 时间复杂度: O(n)，我们只需遍历数组一次。
- 空间复杂度: O(1)，我们只使用了一个额外的变量
result来存储结果。
使用哈希表 (字典)
这种方法也很直观,虽然空间复杂度稍高，但易于理解和实现。
原理
- 遍历数组,使用一个字典（哈希表）来记录每个数字出现的次数。
- 再次遍历数组（或者字典），找到那个出现次数为1的数字。
代码实现
from collections import defaultdict
def singleNumber_hash(nums):
"""
使用哈希表找到只出现一次的数字。
参数:
nums (list[int]): 一个整数列表。
返回:
int: 那个只出现一次的数字。
"""
# 使用 defaultdict 可以在键不存在时自动初始化为0，避免KeyError
counts = defaultdict(int)
# 第一次遍历：统计每个数字的出现次数
for num in nums:
counts[num] += 1
# 第二次遍历：找到出现次数为1的数字
for num in nums:
if counts[num] == 1:
return num
# 如果题目保证有解，理论上不会执行到这里
return -1
# --- 示例 ---
nums1 = [4, 1, 2, 1, 2]
print(f"数组 {nums1} 中只出现一次的数字是: {singleNumber_hash(nums1)}") # 输出: 4
nums2 = [2, 2, 1]
print(f"数组 {nums2} 中只出现一次的数字是: {singleNumber_hash(nums2)}") # 输出: 1
复杂度分析
- 时间复杂度: O(n)，我们遍历了数组两次，仍然是线性时间。
- 空间复杂度: O(n)，在最坏的情况下（除了一个数字外都不同），我们需要存储 n-1 个键值对在字典中。
使用集合
这种方法是哈希表方法的一个变种,可以只遍历一次数组。
原理
- 遍历数组,同时维护一个集合
seen来存放已经出现过的数字。 - 如果当前数字
num不在seen中，就把它加入seen。 - 如果当前数字
num已经在seen中，就把它从seen中移除。 - 遍历结束后,
seen中剩下的唯一一个元素就是我们要找的数字。
代码实现
def singleNumber_set(nums):
"""
使用集合找到只出现一次的数字。
参数:
nums (list[int]): 一个整数列表。
返回:
int: 那个只出现一次的数字。
"""
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
# 集合中最终只会剩下一个元素
return seen.pop()
# --- 示例 ---
nums1 = [4, 1, 2, 1, 2]
print(f"数组 {nums1} 中只出现一次的数字是: {singleNumber_set(nums1)}") # 输出: 4
nums2 = [2, 2, 1]
print(f"数组 {nums2} 中只出现一次的数字是: {singleNumber_set(nums2)}") # 输出: 1
复杂度分析
- 时间复杂度: O(n)，我们遍历数组一次，集合的
add,remove, 和in操作的平均时间复杂度都是 O(1)。 - 空间复杂度: O(n)，和哈希表方法类似，在最坏情况下需要存储 O(n) 个元素。
总结与对比
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 异或 (XOR) | O(n) | O(1) | 最优解，速度快，内存占用极低，代码优雅 | 原理可能不如哈希表直观 |
| 哈希表 | O(n) | O(n) | 思路简单，易于理解和实现 | 需要额外的O(n)空间 |
| 集合 | O(n) | O(n) | 代码相对简洁，只需遍历一次 | 需要额外的O(n)空间 |
在实际面试或生产环境中,强烈推荐使用方法一（异或运算），因为它在时间和空间复杂度上都达到了最优，是解决这个问题的标准答案，哈希表和集合的方法虽然效率稍逊，但作为备选方案或在更复杂的问题变种中（其他数字出现三次）仍然非常有用。
进阶变种问题
singleNumber 问题有很多有趣的变种，
（图片来源网络，侵删）
变种1：除了一个元素只出现一次外，其他每个元素均出现三次。
- 解法：同样可以使用位运算，但更复杂，需要统计每一位上1的个数，如果某一位上1的个数不是3的倍数，那么目标数字在这一位就是1。
- 代码思路：
def singleNumber_II(nums): # ones, twos 分别表示出现一次和两次的位的集合 ones, twos = 0, 0 for num in nums: ones = (ones ^ num) & ~twos twos = (twos ^ num) & ~ones return ones
变种2：除了两个元素只出现一次外，其他每个元素均出现两次。
- 解法：可以扩展异或的思路。
- 先对整个数组进行异或,得到的结果是那两个不同数字的异或值（
a ^ b）。 - 找到这个结果中任意一个为1的位（最右边的1），这个位表示
a和b在这一位上是不同的。 - 根据这一位是0还是1,将原数组分成两组。
- 分别对这两组进行异或,就可以得到
a和b。
- 先对整个数组进行异或,得到的结果是那两个不同数字的异或值（
希望这份详细的解释能帮助你完全理解 Python 中的 singleNumber 问题！
