package Array
// 双指针解法, 时间复杂度: O(n), 空间复杂度: O(1)
func firstMissingPositive(nums []int) int {
size := len(nums)
l, r := 0, size
// nums[0...l-1] -> 1 2 3 ... l, 表示已归位的部分
// nums[r...size-1] -> 表示垃圾区，同时表示在最好情况下1-r这些数字可以全部收集
for l < r {
if nums[l] == l+1 {
// (1) 已归位 -> 继续判断下一个位置
l++
} else if nums[l] <= l || nums[l] > r || nums[nums[l]-1] == nums[l] {
// (2) 已越界或目标位置上的数字已归位 -> 将当前数字分配到垃圾区
nums[l], nums[r-1] = nums[r-1], nums[l]
r--
} else {
// (3) 一般情况 -> 将当前数字与目标位置上的数字进行交换
nums[l], nums[nums[l]-1] = nums[nums[l]-1], nums[l]
}
}
return l + 1
}