經典面試題：從 1~n 中找出 3 個缺失數字的 O(n) 時間 O(n) 空間解法

問題描述

有數組 A 長度 N-3，包含 1 到 N 中除 3 個缺失數字外的所有數，順序打亂。N=10000。要求快速找出 3 個缺失數。

核心思想：空間換時間 —— 標記陣列

利用數字範圍已知（1~N），建立大小 N+1 的輔助陣列 B，下標對應數字值，值為 0/1 標記是否出現。

演算法步驟

1. 分配 int B[N+1] = {0};（索引 1~N 有效，0 忽略）。
2. 遍歷 A，對每個 A[i] 置 B[A[i]] = 1。
3. 再次遍歷 B[1...N]，值為 0 的下標即為缺失數字。

代碼實現

void findMissing(int A[], int n_minus_3) {
    int N = n_minus_3 + 3;
    int *B = (int*)calloc(N + 1, sizeof(int)); // 自動歸零
    
    for (int i = 0; i < n_minus_3; i++) {
        if (A[i] >= 1 && A[i] <= N) B[A[i]] = 1;
    }
    
    printf("缺失的數字：");
    for (int i = 1; i <= N; i++) {
        if (B[i] == 0) printf("%d ", i);
    }
    printf("\n");
    free(B);
}

複雜度分析

• 時間：O(N) 兩次線性掃描。
• 空間：O(N) 輔助陣列（N=10000 约 40KB，極小）。

進階變體與優化方向

位圖優化（節省空間）

若 N 極大（如 1 億），int 陣列 400MB 過大。可用位圖：每個數佔 1 bit，N=1億 僅需 ~12.5MB。

// 位圖版
unsigned char *bitmap = calloc((N >> 3) + 1, 1);
#define SET_BIT(x)   (bitmap[(x)>>3] |=  (1 << ((x)&7)))
#define TEST_BIT(x)  (bitmap[(x)>>3] &   (1 << ((x)&7)))

for (int i=0; i