解題說明
Single Number II
題目描述：給定整數陣列，其中每個元素出現三次，只有一個元素出現一次。找出該元素。要求 O(n) 時間、O(1) 空間。
解題思路：對每個二進制位，統計所有數字該位的 1 的個數，對 3 取模。結果中為 1 的位，就是唯一元素該位的值。進階：使用「two-bit 狀態機」——用 ones 和 twos 兩個變數模擬三進制計數：出現 1 次記在 ones，出現 2 次記在 twos，出現 3 次兩者都清零。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單次遍歷。
空間複雜度：O(1) — 只用兩個整數變數。
虛擬碼
1. Initialize ones = 0, twos = 0 2. For each x in nums: a. ones = (ones XOR x) AND (NOT twos) // add to 'seen once', clear if also in twos b. twos = (twos XOR x) AND (NOT ones) // add to 'seen twice', clear if also in ones 3. Return ones // contains bits seen exactly once mod 3
其他解法
位計數 O(32n)：對 32 個二進制位分別統計，每位計數 mod 3 得到唯一元素對應位 — 正確且易懂，但常數因子 32 比狀態機大。
雜湊計數 O(n)：unordered_map 統計每個數出現次數，找出次數為 1 的 — O(n) 空間，違反題目 O(1) 要求。
延伸思考
- 若每個元素出現 k 次（k 任意），如何一般化狀態機方法？
ones = (ones ^ x) & ~twos的核心邏輯如何防止狀態超過 3 次？- LC 260 Single Number III（兩個不重複元素）使用什麼不同的位元技巧？