LeetCode Single Number - 找出唯一出現一次的數字

題目大意

給定整數數組，除一個元素出現一次外，其餘均出現兩次。找出那個單一元素。要求 O(n) 時間、O(1) 空間。

異或運算性質

• x ^ x = 0
• x ^ 0 = x
• 滿足交換律、結合律

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

代碼 (Java / C++ / Python)

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

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

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums, 0)
        # 或：return functools.reduce(operator.xor, nums)
        # Python 3.8+: return int.__xor__(nums) 不存在，用循環

複雜度

• 時間：O(n)
• 空間：O(1)

總結

位運算經典入門題。異或「無進位加法」特性完美解決成對抵消問題。面試必會，可延伸至 Single Number II/III（三次/兩個單一元素）。