给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数

Question

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

力扣 https://leetcode-cn.com/problems/first-missing-positive/

Answer 1

一、分析

思路如下：
1）如果在 1 到 maxn 之间的数字，映射到哈希数组中；
2）然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案；
3）所有数字都遍历完毕，仍然没有找到，则答案为 $n+1$。

二、源码

#define maxn 500001
int hash[500001], cases = 0;
int firstMissingPositive(int* nums, int numsSize){
    int i;
    ++cases;
    for(i = 0; i < numsSize; ++i) {
        if(nums[i] > 0 && nums[i] < maxn)
            hash[ nums[i] ] = cases;        // (1) 如果在 1 到 maxn 之间的数字，映射到哈希数组中；
    }
    for(i = 1; i <= numsSize; ++i) {
        if(hash[i] < cases) {
            return i;                       // (2) 然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案；
        }
    }
    return numsSize + 1;                    // (3) 所有数字都遍历完毕，仍然没有找到，则答案为 n+1；    
}