LeetCode 136. Single Number - 異或消除成對元素

題目

陣列中只有一個元素出現一次，其餘皆出現兩次。線性時間、O(1) 空間找出該元素。

核心性質

• x ^ x = 0
• x ^ 0 = x
• 異或滿足交換律、結合律：a ^ b ^ a = (a ^ a) ^ b = b

將所有元素異或，成對者抵消為 0，剩下的即為單獨元素。

代碼 (C++ / Java / Python)

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

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int x : nums) ans ^= x;
        return ans;
    }
}

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x,y: x^y, nums, 0)
        # 或簡寫: from functools import reduce; reduce(operator.xor, nums)
        # Python 3.8+: import operator; functools.reduce(operator.xor, nums)

複雜度

• 時間：O(n)，單趟掃描。
• 空間：O(1)，僅一個整數變數。

延伸：出現三次/其他變體

• 「除一個元素出現一次，其餘出現三次」：用 32 位元計數器 cnt[32]，每位 %3 重建答案。
• 「兩個單獨元素」：先全異或得 a^b，取最低位 1 分組，各組異或得 a,b。

異或是位運算消除重複的核心工具，掌握「成對抵消」模板，同類題目秒殺。