LeetCode 41 缺失的第一个正数

题目链接：

https://leetcode.cn/problems/first-missing-positive/

以下是使用Go语言实现外观数列问题的代码：

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for 1 <= nums[i] && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i+1
        }
    }
    return n+1
}

执行用时：44 ms, 在所有 Go 提交中击败了34.96%的用户

内存消耗：8.2 MB, 在所有 Go 提交中击败了26.40%的用户

通过测试用例：174 / 174

题解：

我们可以使用桶排序的思想，将所有正整数按照索引放到对应的位置上。遍历一遍数组，找到第一个位置上没有放置对应数字的索引，这个索引就是没有出现的最小正整数。如果数组中所有的数字都出现了，那么最小正整数就是数组长度加1。

需要注意的是，在遍历数组时，要将负数和大于数组长度的数过滤掉，因为它们不会对最小正整数的计算产生影响。

时间复杂度为 O(n)，空间复杂度为常数级别，符合题目要求。