解题思路

数字的范围是 1~20，非常小，所以我们可以用一个"点名册"来解决问题。

准备一个大小为 21 的数组 v（下标从0到20），就像一份名单，每个格子上写着"这个数字出现过吗"：

• 一开始全都写 0，表示"没出现过"；
• 每读到一个数字 x，就把 v[x] 改成 1，表示"数字 x 出现过了"。

比如读到了 1、3、5，就把 1号格、3号格、5号格都打上勾。

最后从 1 数到 20，凡是格子上还写着 0（没打勾）的数字，就是没出现过的数字，按顺序输出它们。

这种"开一个大数组，每个数字对应一个格子"的方法叫标记法，特别适合数字范围很小的情况，又快又不容易错。

参考代码

// P4478 找出没出现过的数字：用标记数组记录1~20哪些出现过，输出没出现过的
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int v[21] = {0};  // v[i]=1 表示数字i出现过，一开始全都没出现
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v[x] = 1;  // 把数字x的格子打上勾
    }
    int first = 1;  // 控制空格
    for (int i = 1; i <= 20; i++) {
        if (!v[i]) {  // 格子还是0，说明这个数字没出现过
            if (!first) cout << ' ';
            cout << i;
            first = 0;
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

• 时间：读入 n 个数是 O(n)，最后检查 1~20 是常数次（20次），所以总时间是 O(n)。
• 空间：只开了一个大小为 21 的数组，是 O(1)（可以看作固定的、很少的内存）。