數組中唯一只出現一次的數字

---

在一個數組中除了一個數字只出現一次之外，其他數字都出現了三次。

請找出那個只出現一次的數字。

你可以假設滿足條件的數字一定存在。

思考題：

• 如果要求只使用 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）：

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（符合預期）。