網易 2017 校招算法題：找出數組中唯一出現一次的數字（C 語言 O(n) 空間 O(1) 解法）

題目描述

給定整數數組，除一個數字出現 1 次外，其餘均出現 3 次。要求線性時間、常數額外空間找出該唯一數字。例如 {1, 2, 1, 2, 1, 2, 7} 輸出 7。

位運算核心思路

利用二進制位獨立性：對每一位（共 32 位），統計所有數字該位上 1 的總個數。因其餘數字出現 3 次，其每位 1 的貢獻為 3 的倍數。唯一數字的該位值 = 總個數 % 3。將 32 位結果按權重組合即得答案。

完整 C 語言實現

#include <stdio.h>
#include <math.h>

int main() {
    int a[] = {1, 2, 3, 1, 2, 1, 3, 2, 7, 3};
    int n = 10;
    int res = 0, i, j, m;
    for (i = 0; i < 32; i++) { // 遍歷 32 位
        m = 0;
        for (j = 0; j < n; j++) {
            if (a[j] % 2 == 1) m++; // 統計最低位 1 的個數
            a[j] = a[j] >> 1; // 右移一位，下輪檢查高位
        }
        res += (m % 3) * pow(2, i); // 該位結果乘權重累加
    }
    printf("%d", res); // 輸出 7
    return 0;
}

關鍵點解析

• 原地修改數組：通過右移 a[j] >>= 1 依次檢查每一位，無需額外空間，滿足 O(1) 空間限制
• 位獨立性：每位計算互不干擾，最終按 2^i 權重合成
• 負數處理：有符號右移在 C 標準中為實現定義，但主流編譯器（GCC/MSVC）採用算術右移（符號位擴展），對負數同樣適用
• 擴展性：若其餘數字出現 k 次，只需將 m % 3 改為 m % k

複雜度分析

• 時間：O(32 × n) = O(n)，32 為常數
• 空間：O(1)，僅使用固定變量

此解法完美符合題目「線性時間、無額外空間」的嚴格要求，展現位運算在算法設計中的強大威力。