缺少的数字

桶做法

应用场景： A[1~N] 中某个元素是否出现过

• 利用桶来快速知道某个元素是否在序列中出现过

#include <bits/stdc++.h>
using namespace std;

const int N = 2E5 + 1;
int b[N];   
// 桶开多大，取决于 读入元素的个数 还是 查询元素的最大值？
// n = 3, 读入元素 {1000, 1001, 10002}
// A. int b[3]?  -- b[1000]?
// B. int b[10003]? -- b[1000]?
// b[3] = 1，说明数字 3 出现过

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int id;
        cin >> id;
        // 对应 id 球扔进对应 id 桶内
        b[id] = 1;
    }
    // b = {1,1,1,1,1, 0, 1,1,1,1,}
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) {
            cout << i << endl;
        }
    }
    return 0;
}