PAT甲级1144The Missing Number

Posted on | | Visitors:
Words count in article: 320 字 | Reading time ≈ 1 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805343463260160

题解

题目要求

给n（小于1e5）个int，找到最小的不在这些数字里的正整数

注意点

  • map未创建某元素时，如果直接访问，则其value是一个默认值

  • 根据输入样例可知n个数字中可以有重复数字

  • map会按照key自动升序排列

  • 这道题也可以暴力解，创建一个int数组，因为最后要求正整数，所以可以不统计负数

    如果这么做，要注意一个边界情况：不缺数字，比如输入了5个数字，分别是1 2 3 4 5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Problem: PAT Advanced 1144
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805343463260160
// Tags: map

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

int main()
{
    int n;
    cin >> n;
    map<int, int> numCount;
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        numCount[num]++; // 计数，根据输入样例可知n个数字中可以有重复数字
    }
    num = 0;
    while (++num)
        // map未创建某元素时，如果直接访问，则其value是一个默认值
        if (numCount[num] == 0) break;
    cout << num;
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!