AcWing 3820. 未出现过的最小正整数

题目

给定一个长度为 $n$ 的整数数组，请你找出未在数组中出现过的最小正整数。

样例

输入1：[-5, 3, 2, 3]

输出1：1

输入2：[1, 2, 3]

输出2：4

数据范围
$1≤n≤10^5$,
数组中元素的取值范围 $[−10^9,10^9]$。

思路

如何判断使用什么数据结构
通过题目我们可以知道最朴素的方法：

• 首先将所有的输入元素加入到一个集合中
• 然后从 $1$ 到 $n$ 开始枚举，看枚举的数字 $i$ 是否存在于这个集合中
  • 如果不存在，则直接输出 $i$
  • 如果存在，则以此类推，直到找到第一个不存在的数为止
    通过以上思路可以知道，我们的集合需要用到的操作有插入(将所有的元素加入到集合中)、查找(查看枚举的数字是否存在于该集合中)。

综上所述，我们的常规算法为：哈希表

但是又根据题目我们注意到，当集合中的元素全部都出现过时，输出 $n+1$，否则一定输出的时 $1 \sim n$之间的数。
所以答案只会在 $1 \sim n+1$ 之间。
所以我们只需要开一个长度为 $n+1$ 的数组，大于 $n$ 的输入直接舍弃掉即可。

题解

class Solution {
public:
    int findMissMin(vector<int>& nums) {
        int n = nums.size();
        vector<bool> hash(n + 1);
        for (int x: nums)
            if (x >= 1 && x <= n)
                hash[x] = true;
        for (int i = 1; i <= n; i ++ )
            if (!hash[i])
                return i;
        return n + 1;
    }
};