寻找缺失的正整数,这个思路非常有趣,将数组中的每个正整数都放在其自然顺序的下标位置中。即下标为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
}