LeetCode 136 只出現一次的數字：異或運算技巧

題目描述

給定非空整數數組，除了某個元素只出現一次外，其餘元素均出現兩次。找出那個只出現一次的元素。要求：線性時間複雜度、不使用額外空間。

範例：

輸入: [2,2,1]
輸出: 1

輸入: [4,1,2,1,2]
輸出: 4

解題思路：異或運算性質

異或（^）關鍵性質：

• a ^ a = 0（相同為 0）
• a ^ 0 = a
• 滿足交換律、結合律

將數組所有元素異或，成對元素抵消為 0，最終結果即為單獨元素。

時間複雜度：O(n)，空間複雜度：O(1)。

Java 參考實現

public class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            result ^= nums[i];
        }
        return result;
    }
}

Python 參考實現

from functools import reduce
from operator import xor

class Solution:
    def singleNumber(self, nums):
        return reduce(xor, nums)

# 或一行式
# return functools.reduce(lambda x, y: x ^ y, nums)

核心要點總結

• 位運算核心：異或是「不進位加法」，成對抵消特性完美契合題目
• 無額外空間：僅用一個整數變量累積結果
• 變體延伸：

1. LeetCode 137：其他元素出現 3 次 → 需按位統計模 3
2. LeetCode 260：兩個只出現一次的數字 → 異或分組
3. LeetCode 剑指 Offer 56：同 260

異或運算是位運算技巧的皇冠上的明珠，掌握其「成對抵消、順序無關」特性，能秒殺一大類「找單一/找不同」問題。