LeetCode 經典題解：數組中找出兩個只出現一次的數字（異或分組法）

題目：Single Number III

給定整數數組 nums，除兩個數字只出現一次外，其餘數字均出現兩次。找出這兩個只出現一次的數字。要求時間 O(n)、空間 O(1)，順序不限。

核心數學洞察：異或運算性質

• a ^ a = 0
• a ^ 0 = a
• a ^ b = b ^ a (交換律)
• (a ^ b) ^ a = b (結合律)

若將所有數字異或，成對數字抵消為 0，最終結果 xor_all = a ^ b (a、b 為目標數)。

關鍵突破：利用異或結果分組

xor_all 的二進制中至少有一位為 1（因 a ≠ b），該位標誌著 a、b 在此位不同（一為 0，一為 1）。

取 xor_all 的最低位 1 作為分組標誌 mask = xor_all & (-xor_all)：

• 第 1 組：該位為 1 的數字（包含 a 或 b 其中之一）
• 第 2 組：該位為 0 的數字（包含另一個）

每組內部再次異或，成對數字抵消，分別得到 a 和 b。

代碼演進：從標準解到極致優化

版本一：標準可讀寫法

int* singleNumber(int* nums, int numsSize, int* returnSize) {
    int *res = malloc(sizeof(int) * 2);
    int xor_all = 0;
    for (int i = 0; i < numsSize; i++) xor_all ^= nums[i];
    
    int mask = 1;
    while ((mask & xor_all) == 0) mask <<= 1; // 找最低位 1
    
    int a = 0;
    for (int i = 0; i < numsSize; i++)
        if (nums[i] & mask) a ^= nums[i];
    
    res[0] = a;
    res[1] = a ^ xor_all;
    *returnSize = 2;
    return res;
}

版本二：指針算術極致優化 (LeetCode 4ms 級)

int* singleNumber(int* nums, int numsSize, int* returnSize) {
    int xor_all = 0;
    int *end = nums + numsSize;
    int *p = nums;
    
    // 1. 異或累積 (指針遍歷)
    while (p < end) xor_all ^= *p++;
    
    // 2. 取最低位 1 技巧: x & -x
    int mask = xor_all & -xor_all;
    
    // 3. 逆向遍歷分組異或
    int a = 0;
    while (p > nums) {
        int val = *--p;
        if (val & mask) a ^= val;
    }
    
    // 4. 直接復用輸入數組前兩位存結果 (省 malloc)
    nums[0] = a;
    nums[1] = a ^ xor_all;
    *returnSize = 2;
    return nums;
}

優化技巧解析

複雜度分析

• 時間：O(n) - 三次線性遍歷
• 空間：O(1) - 僅用常數額外變量 (優化版復用輸入數組)

測試用例驗證

Input:  [1,2,1,3,2,5]
xor_all = 3^5 = 6 (110)
mask    = 6 & -6 = 2 (010)
Group1 (bit1=1): 2,3,2 → a=3
Group2 (bit1=0): 1,1,5 → b=5
Output: [3,5] or [5,3]

總結

本題展示了位運算分組思想的經典應用：利用異或消除成對干擾，利用差異位分組征服。優化版通過指針算術、補碼技巧、輸入復用，將常數因子壓至極致，是嵌入式開發、高性能庫開發中「極簡風格」的典範。