題目描述:給定整數陣列,其中每個元素出現三次,只有一個元素出現一次。找出該元素。要求 O(n) 時間、O(1) 空間。
解題思路:對每個二進制位,統計所有數字該位的 1 的個數,對 3 取模。結果中為 1 的位,就是唯一元素該位的值。進階:使用「two-bit 狀態機」——用 ones 和 twos 兩個變數模擬三進制計數:出現 1 次記在 ones,出現 2 次記在 twos,出現 3 次兩者都清零。
時間複雜度: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) 要求。
ones = (ones ^ x) & ~twos 的核心邏輯如何防止狀態超過 3 次?