寻找缺失的正整数,这个思路非常有趣,将数组中的每个正整数都放在其自然顺序的下标位置中。即下标为0的放1,下标为1的放2,下标为2的放3……,重复的数和负数都不用理会,经过这么一番整理之后。数组应该看起来是这样的。
#x代表不等于其下标+1的值
#-代表任意值
1 2 3 4 x - - - #缺少5
x - - - - - - - #缺少1
1 2 3 4 5 6 7 8 #缺少9
#实际上,就是找出第一个不等于下标+1的值
代码如下
func firstMissingPositive(nums []int) int {
size := len(nums)
if size == 0 {
return 1
}
var index = 0
for index < size {
value := nums[index]
orderShouldBe := value - 1
//正数 && 小于等于长度 && 不在应该在的位置 && 应该在的位置不是现在的值
if value > 0 && value <= size && index != orderShouldBe && nums[orderShouldBe] != value {
nums[index], nums[orderShouldBe] = nums[orderShouldBe], nums[index]
} else {
index++
}
}
if nums[0] != 1 {
return 1
}
index = 0
for index < size && nums[index] == index+1 {
index++
}
return index + 1
}