從 1 到 n 找出缺失的 3 個數字：空間換時間解法

問題描述

有一組數字，範圍 1 到 n，隨機移除 3 個數字並打亂順序，存放在長度為 n-3 的數組中。要求找出這 3 個缺失的數字，n 假設為 10000，追求時間效率較高的算法。

解決思路：標記數組法

利用額外空間換取 O(n) 時間複雜度：

1. 建立長度 n+1 的整型數組 B，初始化為 0
2. 遍歷原數組 A，對應位置標記為 1：B[A[i]] = 1
3. 再次遍歷 B，值為 0 的下標即為缺失數字

代碼實現

void missnum(int A[], int n_minus_3) {
    int B[n+1] = {0};
    for (int i = 0; i < n_minus_3; i++) {
        B[A[i]] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (B[i] != 1)
            printf("%d ", i); // 輸出缺失的數
    }
}

複雜度分析

• 時間複雜度：O(n)，兩次線性遍歷
• 空間複雜度：O(n)，需額外 n+1 個整數
• 適用於 n 較小（如 10000）且內存充足的場景

替代方案簡述

• 位圖法：用位操作壓縮標記數組，空間減少 32 倍
• 數學法：利用求和、平方和、立方和建立方程組求解，O(1) 空間但涉及大數運算
• 排序法：先排序再掃描，O(n log n) 時間，O(1) 額外空間

摘自 我在這裡