面試題解析：從 1 到 n 中缺失 3 個數字，順序打亂，高效找出缺失值

編輯：關於C語言

問題描述

有一組數字 1 到 n，隨機移除 3 個數字並打亂順序，放入長度為 n-3 的數組。要求找出缺失的 3 個數字，n=10000，算法盡可能快。

解題思路：Bitmap 位圖法

使用一個大小為 n+1 的布爾數組（索引 1~n），初始化為 false。遍歷輸入數組，將對應索引標記為 true。再次掃描位圖，false 的索引即為缺失數字。時間複雜度 O(n)，空間複雜度 O(n)，只需兩次線性掃描，極其高效。

關鍵代碼實現 (C/C++)

#include <iostream>
#include <cstdlib>
using namespace std;

#define N   4000
#define LOST 3

typedef struct { bool bUsed; } NODE_NUM, *PNODE_NUM;

/* 生成測試數據：1~n 中隨機缺失 LOST 個，打亂順序 */
bool GenerateRandomNumSet(int *pData, int nTotalNum, int nLostNum) {
    if (!pData || nTotalNum <= 0) return false;
    PNODE_NUM pList = new NODE_NUM[nTotalNum];
    if (!pList) return false;
    for (int i = 0; i < nTotalNum; ++i) pList[i].bUsed = false;

    for (int i = 0; i < nTotalNum - nLostNum; ++i) {
        int loc = rand() % nTotalNum;
        while (pList[loc].bUsed) {
            loc = (loc + 1) % nTotalNum;
        }
        pData[i] = loc + 1;  // 數值範圍 1~n
        pList[loc].bUsed = true;
    }
    delete[] pList;
    return true;
}

/* 核心解題函數
 * pData: 輸入數組 (長度 nTotalNum)
 * nTotalNum: 輸入數組長度 (n - nLost)
 * pResult: 輸出數組 (長度 nLost)
 * nLost: 缺失個數
 */
void FindLostNum(int *pData, int nTotalNum, int *pResult, int nLost) {
    if (!pData || nTotalNum <= 0 || !pResult || nLost <= 0) return;

    int n = nTotalNum + nLost;  // 原始 n
    PNODE_NUM pList = new NODE_NUM[n + 1];  // 索引 1~n
    if (!pList) return;
    for (int i = 1; i <= n; ++i) pList[i].bUsed = false;

    // 掃描輸入，標記存在的數字
    for (int i = 0; i < nTotalNum; ++i) {
        int val = pData[i];
        if (val >= 1 && val <= n) pList[val].bUsed = true;
    }

    // 收集未標記的數字
    int count = 0;
    for (int i = 1; i <= n && count < nLost; ++i) {
        if (!pList[i].bUsed) pResult[count++] = i;
    }
    delete[] pList;
}

int main() {
    int *pData = new int[N];
    int *pResult = new int[LOST];
    if (!pData || !pResult) return -1;

    GenerateRandomNumSet(pData, N, LOST);  // 實際生成 N-LOST 個
    FindLostNum(pData, N - LOST, pResult, LOST);

    cout << "Lost numbers: ";
    for (int i = 0; i < LOST; ++i) cout << pResult[i] << "\t";
    cout << endl;

    // 驗證
    for (int i = 0; i < N - LOST; ++i) {
        for (int c = 0; c < LOST; ++c) {
            if (pData[i] == pResult[c]) {
                cout << "Verification failed!" << endl;
            }
        }
    }

    delete[] pData;
    delete[] pResult;
    return 0;
}