缺失的第一个正整数 -- LeetCode[41]

给定一个未排序的整数数组，找出其中没有出现的最小的正整数，要求O(n)时间，常数空间。

一道 hard 题，感觉这种题，能想到的话最多到Medium，想不到可能就是Hard了…

在思考的时候一直在纠结于，如何转换题中的条件 “没有出现的最小正整数”。

条件中只有一个约束就是 “最小正整数”。

不考虑时间和空间要求

开辟一个与给出的数组等量的数组空间，排序一下，然后放入这个新的数组。然后从1开始遍历这个数组，出现不连续整数的时候即是需要的结果了。

---

优化：
其实我们只是需要前面连续的数组，后面不连续的部分其实不需要。那么排序其实是不必须的，空间是不是可以使用数组原有的空间呢。

因为整数数组要求从1开始，而数组的索引也是要求从0开始。
那么第一次遍历数组的时候，可以直接把对应的值放入对应的索引下。
再次遍历数组的时候，一旦出现索引和值不一致了，那么就说明，这就是没有出现的最小正整数。

注：

1. 考虑索引和值的偏差（索引从0开始，值从1开始）
2. 复用原数组的时候，从前往后遍历，大于的数组容量的值都可以被忽略
3. 复用原数组，对数据的操作是swap而不是赋值
4. 如果被交换的索引上的值已经是与索引对应了，则放弃交换,否则会引起死循环（exp:[1,1]）

细节是魔鬼，看代码

func firstMissingPositive(nums []int) int {
	for index := 0; index < len(nums); index++ {
		val := nums[index]
		if val > 0 && val <= len(nums) {
			if val != index+1 && nums[val-1] != val {
				nums[val-1], nums[index] = val, nums[val-1]
				index--
			}
		}
	}

	for index := 0; index < len(nums); index++ {
		val := nums[index]
		if val != index+1 {
			return index + 1
		}
	}

	return len(nums) + 1
}