17.3 用陣列儲存資訊：mex 函數

mex（minimum excludant）是競程的常客：給一堆非負整數，回傳沒出現過的最小非負整數。例如 \{3, 0, 1, 10, 3\} 的 mex 是 2——0 有、1 有、2 沒有，答案就是 2。

本站題目〈mex 函數〉：N \le 5 \times 10^5 個數字，0 \le a_i \le 10^9，求 mex。

直覺的做法：從 0 開始逐一檢查「0 出現過嗎？1 出現過嗎？……」，而每次檢查都把數列掃一遍——檢查一次 O(N)，最壞要檢查 N + 1 次，總共 O(N^2)：N = 5 \times 10^5 代進去是 2.5 \times 10^{11}，死當。

慢在哪？慢在「x 出現過嗎」這個問題每次都重新掃。換個方向——用索引當數字，先花一次工把答案全部記下來：

• 開一個標記陣列 seen，讀入數字 x 時把 seen[x] 設成 1。
• 之後「x 出現過嗎」就是查 seen[x]——一步（O(1)）。

但馬上撞到一個問題：a_i 可以到 10^9，seen 開 10^9 格記憶體直接爆炸。這時需要一個關鍵觀察：

¶完整程式碼

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

int main() {
    int n;
    cin >> n;
    vector<int> seen(n + 1, 0);        // 答案最多是 n：比 n 大的數字不用記
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x <= n) {
            seen[x] = 1;               // 用「索引」記住這個數字出現過
        }
    }
    int mex = 0;
    while (seen[mex] == 1) {           // 從 0 往上找第一個沒出現的
        mex++;
    }
    cout << mex << '\n';
    return 0;
}

執行結果（輸入 5 與 3 0 1 10 3）：

2

讀入 O(N)、找答案最多 O(N)——整體 O(N)，跟直覺做法差了整整一個 N 倍。

「用陣列儲存資訊」的適用範圍遠不止 mex：數字出現幾次（把 seen[x] = 1 改成 cnt[x]++）、負數值域（整體平移後當索引）都是同一招。這種「先花一次工把資訊整理成表，之後每問都查表」的思想有個大家族，叫預處理（precomputation）——行列總和這類題目是它的入口，往上還有前綴和等一整套工具，屬於課程裡的重點章節；這裡先記住名字。順帶一提，「數每個數字出現幾次」這個想法再往前一步，就是一種叫計數排序的排序法。