LC136　只出现一次的数字¶

简单通过率 77%python3核心代码模式技巧样例通过牛客 AC位运算数组

讲解章节：位运算

一句话

全体异或，成对的自相抵消，剩下的就是答案。

解题思路¶

这题考什么¶

异或（XOR，按位比较，两位不同得 1、相同得 0，Python 里写作 ^）有三条性质，合起来正好把这题解掉：

a ^ a = 0        任何数与自身异或得 0（每一位都和自己相同）
a ^ 0 = a        0 是异或的单位元
异或满足交换律与结合律，所以一串数异或的结果与顺序无关

题目保证除一个数外其余每个数恰好出现两次。把整个数组从头异或到尾，由交换律可以随意重排成「配对相邻」的形式：

x ^ (a ^ a) ^ (b ^ b) ^ … = x ^ 0 ^ 0 ^ … = x

每一对都抵消成 0，只剩下那个落单的数。不需要知道谁和谁配对，也不需要额外记录任何状态——这正是位运算最典型的用法。位运算的系统讲法见位运算。

「用哈希表计数」或「排序后看相邻」都能得到正确答案，但前者要 O(n) 额外空间，后者要 O(n log n) 时间，都不满足题面「线性时间 + 常量空间」的硬性要求。

数据规模与复杂度¶

1 <= nums.length <= 3e4，-3e4 <= nums[i] <= 3e4。时间 O(n)，一趟扫描；额外空间 O(1)，只有一个累加变量。注意值域含负数，异或必须在能表示负数的整数上做——Python 的 int 是任意精度且按二进制补码语义实现位运算，(-5) ^ (-5) 照样是 0，所以负数不需要任何特殊处理。

坑在哪¶

累加变量的初值只能是 0。0 是异或的单位元，0 ^ nums[0] 恰好等于 nums[0]。若初始化成 nums[0] 再从下标 0 开始异或，第一个数会被算两遍而抵消掉；若初始化成 1 之类的非零值，答案会整体被那个值污染。
这题只对「其余元素恰好出现两次」成立。若某个数出现三次，异或后剩的是它本身而不是 0，结论立刻失效——那属于 LC137 一类的问题，要按位统计出现次数模 3。
别用 sum(nums) - 2 * sum(set(nums)) 之类的求和技巧代替：结论虽也成立，但要建集合，额外空间是 O(n)，违背题面的常量空间要求。
异或运算符是 ^，不是 Python 里的幂运算 **，也不是逻辑或。写错不会报错，只会静悄悄算出别的东西。
严格比对：落单的数唯一，没有多解。

样例复核¶

nums = [4, 1, 2, 1, 2]，逐步异或：

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

结果 4，与题面一致。按交换律重排即 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4，中间那些看似无规律的 5、7、6 只是配对尚未凑齐时的中间态。

参考实现¶

solutions/leetcode/LC136/sol.py
from typing import List, Optional


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 初值必须是 0：它是异或的单位元，0 ^ x == x。
        # 写成 nums[0] 再从头扫，首元素会被异或两次而自相抵消
        ans = 0
        for x in nums:
            # a ^ a == 0，出现两次的数在这条链上成对抵消，
            # 与它们在数组里的位置无关（异或满足交换律与结合律）
            ans ^= x
        # 抵消完只剩那个落单的数
        return ans

LC136 只出现一次的数字¶