41 缺失的第一个整数

题目

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

实例

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

解析

这道题正常的写法是用哈希，但是这道题要求原地，那就使用一种原地哈希的思路.
首先遍历数组，要做的就是数组的每个位置中，存的是每个位置对应的数，不满足的就在对应的位置进行交换.

比如有[3,4,5,-1,1,255]，nums[0] = 3 和nums[0]-1 = 2为下标的值（即nums[2] = 5）进行交换，遍历完成后就保证了：i+1位置存的就是nuns[i]的数，比如nums[0] = 1

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for nums[i] > 0 && nums[i] < n && nums[i] != nums[nums[i]-1] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    for i := 0; i < n; i++ {
        // 如果当前元素不等于它的索引+1,那索引+1就是第一个缺失的正整数
        if nums[i] != i+1 {
            return i + 1
        }
    }
    // 没有的话，缺失的正整数就是数组长度+1
    return n + 1
}