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

频次 ★★★★ · 难度 🟢 · 高频：全厂

题目

非空整数数组，除了某个元素只出现一次，其余都出现两次。找出那个只出现一次的。

思路

异或：a ⊕ a = 0，0 ⊕ a = a。全部异或一遍，结果就是只出现一次的数字。

代码

public int singleNumber(int[] nums) {
    int res = 0;
    for (int n : nums) res ^= n;
    return res;
}

复杂度

• 时间：O(n)
• 空间：O(1)

边界条件

• 长度 1：返回唯一的那个元素
• 全正/全负：异或不受符号影响

变式

• 260. 只出现一次的数字 III：有两个只出现一次的数
• 137. 只出现一次的数字 II：其余出现三次，用位运算统计每位

易错点

• 异或的性质要记牢：a⊕0=a、a⊕a=0、交换律结合律
• 不能用加减法替代——异或是本题的唯一最优解

面试追问

• 如果其他数字出现三次而不是两次？ 逐位统计每个 bit 的出现次数，模 3 取余。不能用异或了

关联题

• 基础：位运算异或性质；进阶：260. 只出现一次的数字 III