技巧⚓︎

只出现一次的数字⚓︎

136. 只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

这道题的核心技巧是异或抵消。

异或满足交换律和结合律，并且有两个关键性质：

$x \oplus x = 0$
$x \oplus 0 = x$

因此，把整个数组中的元素全部异或起来，所有成对出现的数都会两两抵消，最后剩下的就是只出现一次的那个数。

这个方法直接对应题目的两个约束：

只需一次线性遍历，时间复杂度是 $O(n)$ 。
只维护一个异或累积值，额外空间复杂度是 $O(1)$ 。

136. 只出现一次的数字

C++

#include <vector>
using namespace std;

class Solution {
 public:
  int singleNumber(vector<int> &nums) {
    int ans = 0;
    for (int x : nums) {
      // 成对元素异或后会抵消，最后剩下只出现一次的数。
      ans ^= x;
    }
    return ans;
  }
};

两个只出现一次的数字⚓︎

260. 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

你必须设计并实现线性时间复杂度的算法，且仅使用常量额外空间。

如果数组中有两个数各出现一次，其余数都出现两次，那么把所有元素整体异或后，得到的是：

$R = a \oplus b$

由于 $a \neq b$ ，所以 $R \neq 0$ 。这意味着在某个二进制位上， $a$ 和 $b$ 必然不同。取出 $R$ 的任意一个为 $1$ 的位，通常取最低位的 $1$ ：

$\operatorname{lowbit}(R)=R\mathbin{\&}(-R)$

再用这一位把原数组分成两组。因为成对元素在该位上的值相同，所以它们仍会落到同一组内并继续抵消；而 $a$ 和 $b$ 会被分到不同组中，于是问题被拆成两个独立的“只出现一次的数字”。

260. 只出现一次的数字 III

C++

#include <vector>
using namespace std;

class Solution {
 public:
  vector<int> singleNumber(vector<int> &nums) {
    int xorResult = 0;
    for (int num : nums) {
      // 成对元素会抵消，最后得到两个目标值的异或结果。
      xorResult ^= num;
    }

    int mask = 1;
    while ((xorResult & mask) == 0) {
      // 找到一个可以区分这两个目标值的二进制位。
      mask <<= 1;
    }

    int num1 = 0, num2 = 0;
    for (int num : nums) {
      if (num & mask) {
        num1 ^= num;
      } else {
        num2 ^= num;
      }
    }
    return {num1, num2};
  }
};

其余元素出现三次⚓︎

137. 只出现一次的数字 II

给你一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现一次的元素。

你必须设计并实现线性时间复杂度的算法，且不使用额外空间。

如果题目变为“只有一个数出现一次，其余所有数都出现三次”，单纯的整体异或已经不够，因为：

$x \oplus x \oplus x = x$

三次出现不会像两次出现那样被直接消掉。

这类题的做法通常是按二进制位分别统计每一位上 $1$ 的出现次数，再对 $3$ 取模。因为重复元素对每一位的贡献都是 $3$ 的倍数，取模后留下来的就是目标数在该位上的取值。

更常见的常数空间写法是用两个整数 $ones$ 和 $twos$ 维护每个二进制位出现次数对 $3$ 取模后的状态：

$ones$ 表示这一位当前出现了 $1 \bmod 3$ 次。
$twos$ 表示这一位当前出现了 $2 \bmod 3$ 次。

每读入一个新数，就对所有二进制位同步更新状态。某一位一旦累计到 $3$ 次，就会重新回到 $0$ 。遍历结束后， $ones$ 中保留下来的就是只出现一次的那个数。

137. 只出现一次的数字 II

按位计数状态机

C++

#include <vector>
using namespace std;

class Solution {
 public:
  int singleNumber(vector<int> &nums) {
    int ans = 0;
    for (int i = 0; i < 32; ++i) {
      int total = 0;
      for (int num : nums) {
        // 统计第 i 位上 1 的出现次数。
        total += (num >> i) & 1;
      }
      // 对 3 取模后剩下的就是目标值在这一位上的取值。
      if (total % 3 != 0) {
        ans |= 1 << i;
      }
    }
    return ans;
  }
};

C++

#include <vector>
using namespace std;

class Solution {
 public:
  int singleNumber(vector<int> &nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
      // ones 记录当前各二进制位出现 1 次后的状态。
      ones = (ones ^ num) & ~twos;
      // twos 记录当前各二进制位出现 2 次后的状态。
      twos = (twos ^ num) & ~ones;
    }
    // 出现 3 次的位会被自动清空，最终 ones 中剩下目标值。
    return ones;
  }
};

三个只出现一次的数字⚓︎

如果数组中有三个数各出现一次，其余数都出现两次，情况会比两个目标值更复杂。这个问题没有对应的标准 LeetCode 题，但可以沿着异或分组的思路继续构造。

机制⚓︎

假设这三个唯一的数字为 $a, b, c$ 。全局异或结果为：

$X = a \oplus b \oplus c$

对于任意元素 $x$ ，计算其特征值 $\operatorname{lowbit}(x \oplus X)$ 。对于目标数字 $a, b, c$ ，其特征值分别为：

$\operatorname{lowbit}(b \oplus c),\ \operatorname{lowbit}(a \oplus c),\ \operatorname{lowbit}(a \oplus b)$

因为 $a, b, c$ 互不相同，这三个特征值都不为 $0$ 。对数组中所有元素的 $\operatorname{lowbit}(x \oplus X)$ 进行异或累加时，成对元素对应的特征完全相同，仍会两两抵消。

于是最终得到：

$S = \operatorname{lowbit}(b \oplus c) \oplus \operatorname{lowbit}(a \oplus c) \oplus \operatorname{lowbit}(a \oplus b)$

再取：

$L = \operatorname{lowbit}(S)$

根据二进制特性， $L$ 一定能命中三个目标值中的某一个特征位。于是可以再次遍历数组，把满足 $\operatorname{lowbit}(x \oplus X) \mathbin{\&} L \neq 0$ 的元素异或起来，从而恢复出第一个独立数字。

找到这个数字后，剩下两个数字就退化为“两个只出现一次的数字”，可以直接复用上一节的分组异或方法。

步骤⚓︎

对数组全体元素求异或，得到 $X = a \oplus b \oplus c$ 。
初始化变量 $S = 0$ 。遍历数组，计算所有元素的 $\operatorname{lowbit}(x \oplus X)$ 的异或和：

$S \mathrel{\oplus}= \operatorname{lowbit}(x \oplus X)$
计算特征掩码 $L = \operatorname{lowbit}(S)$ 。
寻找第一个数字 $a$ ：遍历数组，若某个元素满足

$\operatorname{lowbit}(x \oplus X) \& L \neq 0$

则对该元素进行异或累加，最终结果即为 $a$ 。
问题降级：计算 $X' = X \oplus a$ ，此时 $X' = b \oplus c$ 。
计算新的分组掩码 $M = \operatorname{lowbit}(X')$ 。
再次遍历原数组，跳过已知的 $a$ 。根据 $x \mathbin{\&} M$ 的结果将剩余元素分为两组，分别进行异或累加，最终结果即为 $b$ 和 $c$ 。

这套构造仍然保持线性时间和常数额外空间。

三个只出现一次的数字（构造）

C++

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
 public:
  vector<int> singleNumberThree(vector<int> &nums) {
    auto lowbit = [](int x) -> unsigned int {
      unsigned int ux = static_cast<unsigned int>(x);
      return ux & (~ux + 1);
    };

    int xors = 0;
    for (int num : nums) {
      // 得到三个目标值的异或结果 a ^ b ^ c。
      xors ^= num;
    }

    unsigned int signature = 0;
    for (int num : nums) {
      // 成对元素的 lowbit(num ^ xors) 相同，异或后会抵消。
      signature ^= lowbit(num ^ xors);
    }

    // 取出一个能够命中其中某个目标值的特征位。
    unsigned int select = signature & (~signature + 1);
    int first = 0;
    for (int num : nums) {
      if (lowbit(num ^ xors) & select) {
        first ^= num;
      }
    }

    // 剩下两个数退化为“两个只出现一次的数字”。
    int rest = xors ^ first;
    unsigned int split = lowbit(rest);
    int second = 0, third = 0;
    for (int num : nums) {
      // 已经恢复出 first，再次异或它没有意义。
      if (num == first) {
        continue;
      }
      if (static_cast<unsigned int>(num) & split) {
        second ^= num;
      } else {
        third ^= num;
      }
    }

    vector<int> ans = {first, second, third};
    sort(ans.begin(), ans.end());
    return ans;
  }
};

扩展到更多目标值⚓︎

当只出现一次的数字个数继续增加到 $k \ge 4$ 时，基于异或的常数空间分离方法通常就不再通用了。

原因在于，异或本质上是 $\mathrm{GF}(2)$ 上的加法。整体异或只能提供非常有限的线性信息。当目标值数量变多时，仅靠少量位特征无法稳定地区分所有未知数，甚至会出现整体异或结果就是 $0$ 的情况，此时连第一步分组依据都无法构造。

因此，更一般的做法通常要回到：

哈希表计数
排序后扫描
特定约束下的按位计数或代数构造

也就是说，136. 只出现一次的数字、260. 只出现一次的数字 III、137. 只出现一次的数字 II 这几题之所以适合位运算，本质上都依赖额外的结构条件：要么重复次数固定为 $2$ ，要么目标值个数足够少，能够被有限个二进制特征稳定分离。

理论上的高阶代数解法：基于

$\text{GF}(2^m)$ 的多项式求根

对于任意已知的 $k$ 值，在不允许使用与输入规模相关的额外内存时，可以通过构建扩展有限域 $\text{GF}(2^m)$ 上的高阶代数方程组来求解。这种方法在数学上等价于通信领域中 BCH 码的纠错解码过程。

假设输入数组的元素为 32 位整数，则可以把它们看成 $\text{GF}(2^{32})$ 中的元素。在这个域上，加法仍然是按位异或，乘法则定义为模某个 32 阶不可约多项式的乘法。

计算伴随式⚓︎

设 $k$ 个只出现一次的数字为 $x_1, x_2, \dots, x_k$ 。对任意整数 $j \in [1, k]$ ，定义伴随式：

$S_j = \bigoplus_{i=1}^{N} E_i^j$

其中 $E_i$ 是数组中的元素，幂运算 $E_i^j$ 使用 $\text{GF}(2^{32})$ 上的域乘法计算。

因为在特征为 $2$ 的域中，加法就是异或，所以成对出现的元素在每个幂次上都会完全抵消：

$y^j \oplus y^j = 0$

因此最终保留下来的只有目标值：

$S_j = x_1^j \oplus x_2^j \oplus \dots \oplus x_k^j$

构建错误定位多项式⚓︎

定义一个多项式：

$\Lambda(z) = (z \oplus x_1)(z \oplus x_2)\cdots(z \oplus x_k) = z^k \oplus \lambda_1 z^{k-1} \oplus \dots \oplus \lambda_k$

它的根正好就是这 $k$ 个未知数。多项式系数 $\lambda_1, \dots, \lambda_k$ 是基本对称多项式。根据牛顿恒等式在特征为 $2$ 的域上的变形，伴随式 $S_j$ 与这些系数之间存在严格的代数关系。

在工程实现中，通常会通过 Berlekamp-Massey 一类的方法，从 $S_1, S_2, \dots, S_k$ 恢复出多项式的全部系数。

多项式求根⚓︎

当 $\Lambda(z)$ 的系数确定后，就需要在 $\text{GF}(2^{32})$ 中求它的全部根。由于整个域的规模很大，工程上通常使用钱氏搜索的变体，或 Cantor-Zassenhaus 这类有限域多项式分解算法来完成求根。

求出的 $k$ 个根，就是数组中只出现一次的那 $k$ 个数字。

性能与限制⚓︎

空间复杂度：需要存储 $k$ 个伴随式和 $k$ 个多项式系数，因此是 $O(k)$ 。当 $k$ 视为常数时，可以记为 $O(1)$ 。
时间复杂度：计算伴随式需要 $O(kN)$ 次域运算；多项式恢复和求根与 $N$ 无关，但常数极大。
工程意义：虽然该方法在理论上可以作为常数空间构造成立，但 $\text{GF}(2^{32})$ 上的域乘法和高阶多项式求根开销极高，在常规软件工程中几乎没有实用价值，更适合作为代数编码理论视角下的理论极限说明。

多数元素⚓︎

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n / 2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

这道题对应摩尔投票。

维护两个量：

$candidate$ 表示当前候选值。
$count$ 表示候选值相对于其他元素的净胜票数。

遍历数组时：

如果当前元素等于候选值，则 $count \leftarrow count + 1$ 。
如果当前元素不等于候选值，则 $count \leftarrow count - 1$ 。
如果 $count = 0$ ，说明前面这一段中候选值和其他元素已经完全抵消，后续可以从下一个位置重新选择候选值。

为什么最后留下来的数一定是多数元素：

因为多数元素的出现次数严格大于其余所有元素出现次数之和。无论如何做两两抵消，它都不可能被完全消掉，所以最终候选者只能是它。

169. 多数元素

C++

#include <vector>
using namespace std;

class Solution {
 public:
  int majorityElement(vector<int> &nums) {
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.size(); i++) {
      if (count == 0) {
        // 前面的票数已经完全抵消，从当前位置重新选择候选值。
        candidate = nums[i];
      }
      count += nums[i] == candidate ? 1 : -1;
    }
    return candidate;
  }
};

颜色分类⚓︎

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置排序函数的情况下解决这个问题。

这道题使用荷兰国旗问题的三指针划分。

遍历过程中维护三个区间：

$[0, left)$ 全部是 $0$
$[left, current)$ 全部是 $1$
$(right, n - 1]$ 全部是 $2$

当前处理位置是 $current$ ，分类规则如下：

如果 $nums[current] = 0$ ，它应该被放到左侧区间，于是与位置 $left$ 交换，然后 $left$ 和 $current$ 同时右移。
如果 $nums[current] = 1$ ，它本来就在中间区间，只需让 $current$ 右移。
如果 $nums[current] = 2$ ，它应该被放到右侧区间，于是与位置 $right$ 交换，然后 $right$ 左移。

这里有一个关键细节：当 $nums[current] = 2$ 时，交换后不能立刻移动 $current$ 。因为从右侧换过来的数还没有检查，必须在当前位置继续分类。

整个过程只扫描一次数组，时间复杂度是 $O(n)$ ，额外空间复杂度是 $O(1)$ 。

75. 颜色分类

C++

#include <vector>
using namespace std;

class Solution {
 public:
  void sortColors(vector<int> &nums) {
    int left = 0;
    int current = 0;
    int right = nums.size() - 1;
    while (current <= right) {
      if (nums[current] == 0) {
        swap(nums[left], nums[current]);
        left++;
        current++;
      } else if (nums[current] == 2) {
        swap(nums[current], nums[right]);
        // 右侧换回来的元素还未检查，current 不能前进。
        right--;
      } else {
        current++;
      }
    }
  }
};

下一个排列⚓︎

31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列。

必须原地修改，只允许使用额外常数空间。

这道题的关键不是枚举排列，而是直接定位“下一次变大”的最小修改位置。参考排列，其中包含“上一个排列与下一个排列”的统一写法。

从右向左扫描，先找到第一个满足

$nums[i - 1] < nums[i]$

的位置。这里的 $i - 1$ 就是需要提升的支点。之所以从右往左找，是因为右侧后缀已经是字典序最大的非递增序列；如果更右边还能调整出更大的排列，就不会轮到当前支点。

找到支点后，需要在后缀中找一个刚好比 $nums[i - 1]$ 大的数进行交换。因为后缀本身是非递增的，所以从左到右找到第一个不再大于支点的位置，再回退一位，就得到了后缀中最靠右、同时又大于支点的元素。这样交换后，前缀增长得最少。

交换完成后，原来的后缀仍然是非递增的。要得到紧邻当前排列的下一个排列，还需要把后缀改成字典序最小的形式，也就是直接反转为升序。

如果整段数组本来就是非递增的，例如 $[3,2,1]$ ，说明它已经是字典序最大的排列。此时没有更大的结果，只需整体反转，得到字典序最小的排列。

31. 下一个排列

C++

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
 public:
  void nextPermutation(vector<int> &nums) {
    int n = nums.size();
    int i = n - 1;
    for (; i >= 1; --i) {
      if (nums[i] > nums[i - 1]) {
        break;
      }
    }
    // 整体非递增，当前已经是字典序最大排列。
    if (i == 0) {
      reverse(next(nums.begin(), i), nums.end());
      return;
    }
    int j = i;
    for (; j < n; ++j) {
      // 后缀非递增，回退一位后就是最后一个大于支点的元素。
      if (nums[j] > nums[i - 1]) {
        continue;
      }
      break;
    }
    j -= 1;
    swap(nums[i - 1], nums[j]);
    // 交换后将后缀变成最小升序排列。
    reverse(next(nums.begin(), i), nums.end());
  }
};

寻找重复数⚓︎

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内，可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

不能更改原数组，并且只用常量级 O(1) 的额外空间。

这道题的关键是把数组视为一个函数图，而不是数组统计题。

把每个下标看成一个节点，从节点 $i$ 连一条边到 $nums[i]$ 。由于数组长度是 $n + 1$ ，但所有 $nums[i]$ 都落在区间 $[1, n]$ ，所以一共有 $n + 1$ 个位置，却只指向 $n$ 个有效值。根据抽屉原理，至少有两个不同的下标会指向同一个值，这正是重复数出现的地方。

从节点 $0$ 出发不断跳转：

$0 \rightarrow nums[0] \rightarrow nums[nums[0]] \rightarrow \cdots$

因为后续节点始终落在区间 $[1, n]$ ，而节点数量有限，这条路径一定会进入一个环。并且，这个环的入口恰好就是重复的那个值。

原因是重复值 $d$ 意味着至少有两个不同位置都把边指向 $d$ 。在从 $0$ 出发的路径里，这会表现为两条路径汇入同一个节点，从而形成一个带入口的环结构。于是问题就转换为求链表环的入口。

Floyd 判环分两步完成：

第一阶段，快慢指针在环内相遇。
第二阶段，一个指针回到起点 $0$ ，另一个留在相遇点，然后两者同步前进，再次相遇的位置就是环入口，也就是重复数。

整个过程不修改数组，时间复杂度是 $O(n)$ ，额外空间复杂度是 $O(1)$ 。