缺失的第一个正数
func firstMissingPositive(nums []int) int {
n := len(nums)
// left: left 左侧已归位
// right: right 右侧为垃圾区
// 归位: [1, 2, 3, ...]，即：nums[i] == i + 1
left, right := 0, n - 1
for left <= right {
if nums[left] == left + 1 { // 已归位
left++
} else if nums[left] < left + 1 { // 垃圾
nums[left], nums[right] = nums[right], nums[left]
right--
} else if nums[left] - 1 > left && nums[left] - 1 <= right {
// 要放的位置已经是正确的值了，那么当前值就是垃圾
if nums[nums[left] - 1] == nums[left] {
nums[left], nums[right] = nums[right], nums[left]
right--
} else {
// 放到正确的位置
nums[left], nums[nums[left] - 1] = nums[nums[left] - 1], nums[left]
}
} else { // 垃圾
nums[left], nums[right] = nums[right], nums[left]
right--
}
}
return left + 1
}