題目描述:整數陣列 nums 中,恰好有兩個元素只出現一次(設為 a 和 b),其餘所有元素都出現兩次。找出 a 和 b,以任意順序回傳。要求線性時間、常數額外空間。
解題思路:XOR 位元操作分組。
第一步:對陣列所有元素做 XOR,得到 diff = a ^ b。由於相同數字 XOR 為 0,出現兩次的數字全部抵消,最終 diff 正是 a 和 b 的 XOR 結果。
第二步:diff != 0,代表 a 和 b 在 diff 為 1 的某個位元上不同。取 diff 的最低位 1:mask = diff & (-diff)(利用補數性質隔離最低位)。
第三步:用 mask 將陣列分成兩組:
a 和 b 必定分屬兩組(因為它們在該位元上不同)。每組內出現兩次的數字互相抵消,各組 XOR 的結果就是 a 和 b。
時間複雜度:O(n) — 兩次線性遍歷,第一次求 diff,第二次分組 XOR,各為 O(n)。
空間複雜度:O(1) — 只使用 diff、mask、a、b 等常數個變數,不需要額外的陣列或雜湊表。
Function singleNumber(nums):
// Step 1: XOR all elements to get a XOR b
diff = 0
For each x in nums:
diff = diff XOR x
// Step 2: Isolate the lowest set bit of diff
// This bit differs between a and b
mask = diff AND (-diff)
// Step 3: Split into two groups by mask, XOR each group
a = 0, b = 0
For each x in nums:
If x AND mask is non-zero:
a = a XOR x
Else:
b = b XOR x
Return [a, b]雜湊表計數 O(n) 時間,O(n) 空間:用 unordered_map 統計每個數字出現的次數,最後回傳出現次數為 1 的兩個數字。邏輯最直觀,但違反題目的常數空間要求。
排序法 O(n log n) 時間,O(1) 空間:將陣列排序後,相同數字相鄰。逐對掃描,若 nums[i] != nums[i+1] 則 nums[i] 為答案之一。可在 O(1) 空間內完成,但時間複雜度退化至 O(n log n),不滿足線性時間要求。
任意位元(非最低位)的分組:第二步不一定要取最低位 1,任何 diff 中為 1 的位元都可作為分組依據。diff & (-diff) 只是最簡潔的取法(Brian Kernighan's trick)。也可用 diff & ~(diff - 1) 或逐位掃描找到第一個 1 的位置。
diff & (-diff) 能取最低位 1 的原因是什麼?補數(二補數)的哪個性質保證了這個等式?請從二進位角度說明。