LeetCode 136 Single Number：位運算 XOR 找出唯一出現一次的數字

題目描述

給定整數陣列，除一個元素外其餘皆出現兩次。找出那個只出現一次的元素。要求線性時間、不使用額外空間。

核心洞察：XOR 性質

• a ^ a = 0
• a ^ 0 = a
• 交換律、結合律成立

所有成對數字 XOR 後抵消為 0，剩下的即為單獨數字。

代碼實作

class Solution {
public:
    int singleNumber(vector& nums) {
        int result = 0;
        for (int n : nums) result ^= n;
        return result;
    }
};

複雜度

• 時間：O(n)，單次遍歷。
• 空間：O(1)，僅一個整數變數。

延伸題目

• LeetCode 137 Single Number II：其餘出現三次，需用位計數器（每 bit 模 3）。
• LeetCode 260 Single Number III：有兩個單獨數字，先 XOR 全陣列得 a^b，找一個為 1 的 bit 分組再各自 XOR。