LeetCode Single Number III - 找出兩個只出現一次的數字

題目大意

數組中恰有兩個元素出現一次，其餘均出現兩次。找出這兩個元素。O(n) 時間、O(1) 空間。

核心思路：分組異或

1. 先將所有元素異或，得到 xorAll = a ^ b (a,b 為兩個單一元素)。xorAll != 0，至少有一位為 1。
2. 取 xorAll 的最低位 1：bit = xorAll & (-xorAll) (或 xorAll & ~(xorAll-1))。該位上 a 和 b 必異（一 0 一 1）。
3. 根據該位將數組分為兩組：該位為 1 的、該位為 0 的。a、b 落入不同組；成對元素落入同組（因相同數該位相同）。
4. 分別對兩組異或，即得 a 和 b。

代碼 (Java / C++ / Python)

public class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int n : nums) xorAll ^= n;
        int bit = xorAll & (-xorAll); // 最低位 1
        int a = 0, b = 0;
        for (int n : nums) {
            if ((n & bit) != 0) a ^= n;
            else b ^= n;
        }
        return new int[]{a, b};
    }
}

class Solution {
public:
    vector singleNumber(vector& nums) {
        int xorAll = 0;
        for (int n : nums) xorAll ^= n;
        int bit = xorAll & -xorAll;
        int a = 0, b = 0;
        for (int n : nums) {
            if (n & bit) a ^= n;
            else b ^= n;
        }
        return {a, b};
    }
};

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_all = reduce(xor, nums)
        bit = xor_all & -xor_all
        a = b = 0
        for n in nums:
            if n & bit: a ^= n
            else: b ^= n
        return [a, b]

複雜度

• 時間：O(n) — 兩次遍歷。
• 空間：O(1) — 只有常數變量。

總結

Single Number 系列終極形態：利用異或性質 + 位分組，將「兩個單一元素」問題降維為兩個「一個單一元素」子問題。面試必會，代碼極短、邏輯優美。可延伸討論：若三個單一元素如何分組（需更多位）、有符號整數負數處理（同樣適用，補碼表示下位運算無差別）。