A1144.md

A1144 The Missing Number

1.题意理解

给出一堆整数，找出不在其中的最小正整数

2.思路分析

本题是408算法大题原题，使用哈希思想解决。

由于n个整数，最佳情况是1~n连续出现，这样不在其中的最小整数即为n+1，反之必有空缺。

3.参考代码

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

const int N = 100100;
unordered_map<int, int> mp;

int main()
{
    int n, x;
    scanf("%d", &n);

    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        if(x >= 0)
            mp[x] = 1;
    }

    for(int i = 1; i <= n; i++)
        if(!mp[i])
        {
            printf("%d\n", i);
            return 0;
        }

    printf("%d\n", n + 1);

    return 0;
}