essay
hot100-缺失的第一个正数
#算法
hot100——缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <=
- <= nums[i] <= - 1
解法
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
// nums[i]和nums[nums[i] - 1]分别代表的是当前元素和它应该在的位置上的元素
// nums[i]-1是应该在的位置的下标
// 如[3, 1, 2, 4] 3应该在2的位置上，所以要交换3和2（下标0和2）
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]
}
}
// 全部交换完后，从开头检查是不是都在对应的位置上，第一个满足 nums[i] != i+1 的位置，缺失的正数即为 i+1
for i := 0; i < n; i++ {
if nums[i] != i+1 {
return i+1
}
}
// // 如果所有位置都正确，则缺失的是 n+1
return nums[n-1]+1
}