剑指offer56_数组中唯一只出现一次的数字

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

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

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

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

思考题：

• 如果要求只使用 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; // 初始化状态为 00
        
        for (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）：

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

中间位：

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

最高位：

1. 输入 0（来自 2）：状态保持 00
2. 输入 0（来自 2）：状态保持 00
3. 输入 0（来自 3）：状态保持 00
4. 输入 0（来自 2）：状态保持 00
   • 最终状态 00 → 该位为 0

最终结果：二进制 011 = 十进制 3。
输出：3（符合预期）。