数组中唯一只出现一次的数字

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题：

如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

数据范围

数组长度 [1,1500]。
数组内元素取值范围 [0,1000]。

样例

输入：[1,1,1,2,2,2,3,4,4,4]输出：3

算法思路

核心思路是使用位运算和状态机的概念，通过两个变量（a 和 b）记录每个比特位出现次数的状态（模 3 的结果）。状态转移规则如下：

状态定义：用 (b, a) 表示每个比特位的状态：
- 00：该位出现次数为 0 或 3 的倍数。
- 01：该位出现 1 次。
- 10：该位出现 2 次。
状态转移（输入当前数字 x 的某一位）：
- 输入 0：状态保持不变。
- 输入 1：状态按 00 → 01 → 10 → 00 循环变化。
更新规则：
- a = (a ^ x) & ~b
- b = (b ^ x) & ~a（注意：此处 a 是已更新后的值）

最终，a 记录了所有出现一次的数字的比特位，即所求结果。

时间复杂度：

O(n)：遍历数组一次，n 为数组长度。

空间复杂度：

O(1)：仅使用两个额外变量 a 和 b。

class Solution {
public:int findNumberAppearingOnce(vector<int>& nums) {int a = 0, b = 0; // 初始化状态为 00for (auto x : nums) { // 遍历每个数字// 更新规则（注意顺序）：// 1. 更新 a：利用当前状态 b 和输入 x//    - 当 b=0 时，a 与 x 异或（记录新状态）//    - 当 b=1 时，a 被置 0（状态 10 遇到 1 后变为 00）a = (a ^ x) & ~b;// 2. 更新 b：利用更新后的 a 和输入 x//    - 当 a=0 时，b 与 x 异或（记录新状态）//    - 当 a=1 时，b 被置 0（确保状态合法）b = (b ^ x) & ~a;}return a; // 最终 a 存储出现一次的数字}
};

实例演示

假设输入数组 nums = [2, 2, 3, 2]，所有数字的二进制表示：

2 → 010
3 → 011

逐步计算每个比特位的状态变化：

最低位（LSB）：

输入 0（来自 2）：
- 初始状态 (b,a) = (0,0)
- 更新后：a = (0^0)&~0 = 0, b = (0^0)&~0 = 0 → 状态 00
输入 0（来自 2）：状态保持 00
输入 1（来自 3）：
- a = (0^1)&~0 = 1, b = (0^1)&~1 = 0 → 状态 01
输入 0（来自 2）：状态保持 01
- 最终状态 01 → 该位为 1

中间位：

输入 1（来自 2）：
- a = (0^1)&~0 = 1, b = (0^1)&~1 = 0 → 状态 01
输入 1（来自 2）：
- a = (1^1)&~0 = 0, b = (0^1)&~0 = 1 → 状态 10
输入 1（来自 3）：
- a = (0^1)&~1 = 0, b = (1^1)&~0 = 0 → 状态 00
输入 1（来自 2）：
- a = (0^1)&~0 = 1, b = (0^1)&~1 = 0 → 状态 01
- 最终状态 01 → 该位为 1