Single Number
你会得到一个列表 nums，其中每个值都恰好出现两次，只有一个值只出现一次。返回只出现一次的值。
函数
- numsinteger-array
- 一个列表，其中除了一个值以外，其他每个值都出现了两次
- 返回值integer
- 只出现一次的值
约束条件
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- 每个值都恰好出现两次，只有一个值恰好出现一次。
示例
- 输入
- nums = [8, 3, 8]
- 输出
- 3
- 解释
- 8 出现了两次，3 出现了一次，所以答案是 3。
- 输入
- nums = [5, -2, 7, 5, 7]
- 输出
- -2
- 解释
- 5 和 7 各出现两次，-2 是唯一只出现一次的值。
- 输入
- nums = [42]
- 输出
- 42
- 解释
- 只有一个值的列表没有任何配对，因此这个值就是答案。
进阶
如果除了一个值之外，其他每个值都出现 3 次呢？仅靠 XOR 已经无法抵消这些出现 3 次的值。你还能在 O(n) 时间内用 O(1) 的额外内存找到这个只出现 1 次的值吗？
提示
逐个打开提示，每个都会多透露一点。
如果每一对相等的值都能消失，最后就只剩下答案了。有没有一种运算可以把两个相等的数字变成空无？
XOR 的运算规则是：
x ^ x的结果是0，x ^ 0的结果是x。它还不受顺序影响，因此同一个值的两份副本不必相邻也能相互抵消。保留一个初始值为
0的变量。将nums中的每个值都与它进行 XOR 运算，然后返回它。不需要映射，也不需要排序。
题解
哈希表通过计数找到没有配对的值，但哈希表会随着列表增长。XOR 不需要计数，因为一个值与自身进行 XOR 运算会得到 0。将整个列表中的值逐个进行 XOR 运算，每一对都会相互抵消，只留下一个值，并存储在一个变量中。
通过扫描统计每个值
结果正确，但无法在最大的测试中运行完毕
思路
对于每个值，扫描整个列表并统计它出现的次数；返回第一个出现次数为 1 的值。次数的计算符合答案的定义，因此结果正确。n 个值中的每一个都会触发一次对 n 个值的扫描：当唯一的值位于包含 9,999 个元素的列表末尾时，需要进行近 10^8 次比较。
算法
- 遍历
nums中的每个值。 - 扫描整个列表，统计与该值相等的值的数量。
- 如果数量是 1，就返回该值。
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0使用哈希表计数
思路
用哈希映射统计每个值的出现次数，只需遍历一遍。对于 [5, -2, 7, 5, 7]，映射最终为 5 → 2、-2 → 1、7 → 2，遍历映射后可以找到 -2。
每个值都需要更新一次映射，因此时间复杂度为 O(n)。映射中大约有 n/2 个条目，需要 O(n) 的额外内存。C 没有内置的映射，因此可以用一个以 value + 10^4 为索引的计数器数组来实现相同的功能。
算法
- 创建一个从值到计数的空映射。
- 对于
nums中的每个值，将其计数加 1。 - 遍历映射，并返回计数为 1 的值。
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR 所有值
思路
XOR 会在两个输入不同时将对应位设为 1。因此，x ^ x = 0、x ^ 0 = x，而且运算顺序无关紧要。
用一个初始值为 0 的变量对整个列表执行 XOR。重新组合这些运算，让每个值都和它的配对值相遇：每一对都会变成 0，而 0 ^ single 会留下那个单独的值。对于 [8, 3, 8]：0 ^ 8 = 8，然后 8 ^ 3 = 11，接着 11 ^ 8 = 3。循环只读取每个值一次，并且只保留一个变量：时间复杂度为 O(n)，额外空间复杂度为 O(1)。
算法
- 将
result设为 0。 - 对于
nums中的每个值，将result设为result ^ value。 - 返回
result。
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
易错点和边界情况
- 将
result初始化为nums[0]，然后遍历每个值，包括索引 0。第一个值被异或了两次，会相互抵消。从 0 开始，或者跳过索引 0。 - 排序后每次比较相邻的两个值，却忘了那个单独的值可能在最后。在
[1, 1, 2]中，检查的每一对都相同，答案是剩下的 2。 - 当值可能出现奇数次时，仍然使用 XOR 循环。它只能抵消出现偶数次的值，所以对于
[4, 4, 4, 9]，它会返回4 ^ 9 = 13，而不是 9。
常见问题3
Single Number 的时间复杂度是多少？
XOR 解法的运行时间为 O(n)，额外空间复杂度为 O(1)。哈希表的时间复杂度也是 O(n)，但需要 O(n) 的内存。每次重新扫描来统计每个值需要 O(n²) 的时间。
XOR 答案适用于负数吗？
是的。XOR 对存储数字的位进行运算，而负数以二进制补码形式存储。两个相等的负数具有相同的位，因此它们会像正数一样抵消。在 [5, -2, 7, 5, 7] 中，结果是 -2。
你能不用 XOR，而用求和来解决“单个数字”吗？
是的。2 × sum(distinct values) - sum(nums) 就是那个只出现一次的值：每个成对的值在两边各计算两次，那个只出现一次的值在一边计算两次，在另一边计算一次。对于 [5, -2, 7, 5, 7]，结果是 2 × 10 - 22 = -2。存储不同值的集合需要 O(n) 内存，而 XOR 可以避免这一点。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def singleNumber(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [8, 3, 8]
预期输出
3