260. 只出现一次的数字 III（Single Number III）
频次 ★★★ · 难度 🟡 · 高频：字节
题目
两个元素只出现一次，其余各出现两次。找出这两个元素。
思路
先全部异或得到 xor = a ^ b。取 xor 最低位的 1（xor & -xor）把数组分成两组，每组各自异或得到两个数。
代码
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int n : nums) xor ^= n;
int mask = xor & -xor; // 最低位的 1
int a = 0, b = 0;
for (int n : nums) {
if ((n & mask) == 0) a ^= n;
else b ^= n;
}
return new int[]{a, b};
}复杂度
- 时间：O(n)，两趟遍历
- 空间：O(1)——这是本题相对哈希表计数的全部价值
边界条件
a和b必然不同，所以xor = a ^ b != 0，mask一定存在。这是分组能成立的前提xor为Integer.MIN_VALUE：-xor溢出后仍等于自身，xor & -xor恰好还是最高位那个 1，结果正确- 数组只有两个元素：第一趟
xor = a ^ b，第二趟各分一组，直接得解 - 出现两次的元素必然落在同一组（它们的每一位都相同），组内异或自动消掉
变式
- 136. 只出现一次的数字：只有一个落单，全体异或即可，不需要分组
- 其余元素出现三次，一个出现一次：异或失效（三个相同数异或还剩一个）。改成按位统计每一位上 1 的个数模 3，或用「两个状态变量模拟三进制计数器」
- 三个元素只出现一次：
xor是三者异或，无法简单二分。要先找到一个必然存在的、能把三者分开的位，做法复杂得多 - 求两个数中较小的那个：分组完拿到 a、b 后直接比
易错点
xor & -xor取的是最低位的 1，不是最高位。任何一个为 1 的位都能用来分组，取最低位只是因为这个写法最短- 分组的判据是
(n & mask) == 0，不是(n & mask) == 1。mask可能是0b1000，与出来的结果是 8 不是 1 - 第二趟遍历要走完整数组，不能只走一半——出现两次的元素也要参与异或才能被消掉
- 不要先把数组按 mask 物理分成两个数组再异或，那会多 O(n) 空间，白白丢掉本题的核心优势
面试追问
x & -x为什么能取出最低位的 1：-x是~x + 1。取反后最低位的 1 变成 0、其右边的 0 全变 1；再加 1 使这些位进位回来，结果是「最低位的 1 保持，其左边所有位与 x 相反」。与一下，只剩那个 1。这个式子在树状数组里叫lowbit，是它的核心。- 为什么异或能消掉成对的数：异或满足交换律、结合律，且
a ^ a = 0、a ^ 0 = a。所以全体异或等价于「把所有成对的消掉，剩下落单的」。异或的自反性就是一个天然的、O(1) 空间的『配对消除器』。 - 分组的正确性怎么证：
mask位上 a 和 b 必然一个是 0 一个是 1（否则该位异或为 0，不会被xor选中）。所以 a、b 必然分属两组；而任何出现两次的数，两次都落进同一组。于是每组恰好是「一个落单 + 若干成对」，退化成 136。 - 有没有不用位运算的 O(1) 空间解：没有通用解。哈希表 O(n) 空间，排序 O(n log n) 时间且破坏原数组。位运算在这里不是炫技，是唯一能同时做到 O(n) 时间 + O(1) 空间的路径。