1144. The Missing Number.md

【PAT A-1144】The Missing Number

题意概述

给定 N 个整数，要求找到不在这些整数中的最小正整数。

输入输出格式

输入第一行给出正整数 N，接下来一行，给出 N 个正整数。

输出不在这些整数中的最小正整数。

数据规模

$$N\le {10}^5$$

算法设计

将这 N 个正整数存入一个 unordered_set 中，然后从 1 开始枚举，第一个不在 unordered_set 中的正整数即为所求。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ai;
    cin >> ni;
    unordered_set<gg> us;
    for (gg i = 0; i < ni; ++i) {
        cin >> ai;
        us.insert(ai);
    }
    for (gg i = 1;; ++i) {
        if (not us.count(i)) {
            cout << i;
            break;
        }
    }
    return 0;
}