Single Number
題目描述
給定一個非空整數陣列，除了某個元素只出現一次外，其餘每個元素都出現兩次。找出那個只出現一次的元素。要求 O(1) 空間。
輸入：nums = [2,2,1]
輸出：1
輸入：nums = [4,1,2,1,2]
輸出：4
解題思路
初始化
result = 0（XOR 的恆等元素，0 XOR 任何數 = 那個數）
逐一 XOR
遍歷陣列，每個元素和 result 做 XOR：result ^= nums[i]
成對消除
相同數字 XOR 為 0（a^a=0），成對出現的數字在累積過程中互相抵消
剩餘即答案
所有成對數字消除後，result 中只剩下那個出現一次的數字
程式碼
C#
public class Solution {
public int SingleNumber(int[] nums) {
int result = 0;
foreach (int num in nums) {
result ^= num; // XOR：相同的數字會互相消除
}
return result;
}
}TypeScript
function singleNumber(nums: number[]): number {
return nums.reduce((result, num) => result ^ num, 0);
}Python
from functools import reduce
from operator import xor
def singleNumber(nums: list[int]) -> int:
return reduce(xor, nums)複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
遍歷陣列一次做 n 次 XOR 運算，每次 O(1)，因此時間 O(n)。只用一個整數變數累積結果，空間 O(1)。
邊界情況
- 陣列只有一個元素：例如
[7]，0 XOR 7 = 7，直接回傳該元素 - 包含負數：例如
[-1,1,1]，XOR 位元運算對負數（補碼表示）同樣適用，結果為 -1 - 包含 0：例如
[0,1,1]，0 XOR 0 = 0，成對的 1 消除後剩 0
圖解
圖表展示逐步 XOR 的過程：每個數字依序 XOR 進 result。雖然中間結果看似雜亂（4→5→7→6），但成對的 1 和 2 最終互相消除，只剩下唯一出現一次的 4。
進階觀點
💡面試追問
-
Q: 137. Single Number II 怎麼解？ A: 其他數字出現三次，用「逐位元統計」：對每個 bit 位統計所有數字在該位上 1 的個數，mod 3 後剩下的就是唯一數字的 bit。也可以用「有限狀態機」用兩個變數 ones/twos 追蹤每個 bit 出現次數。
-
Q: 260. Single Number III 怎麼解？ A: 有兩個數字 a, b 各出現一次。先全部 XOR 得到
a^b，取其 lowbit（x & -x）作為分組依據。這個 bit 位上 a 和 b 一定不同，用它將所有數字分成兩組，各組內再 XOR 就分別得到 a 和 b。 -
Q: 為什麼不用 HashSet？ A: HashSet 需要 O(n) 額外空間來存見過的元素，而 XOR 只要一個整數變數就能達到 O(1) 空間。題目要求 O(1) 空間，XOR 是唯一滿足的做法。
-
Q: XOR 的核心性質有哪些？ A: 交換律
a^b = b^a、結合律(a^b)^c = a^(b^c)、自反性a^a = 0、恆等性a^0 = a。自反性和恆等性是成對消除的關鍵。
理解測驗
🤔 為什麼 XOR 所有元素後成對的數字會消失？
🤔 如果陣列中有兩個數字各出現一次（其餘都出現兩次），全部 XOR 後得到什麼？