查找数组中缺失的最小正整数 O(n)

 1// findSmallestMissingNumber 查找数组中缺失的最小正整数
 2func findSmallestMissingNumber(nums []int) int {
 3	n := len(nums)
 4
 5	// 遍历数组，将每个数字放到它应该在的位置上
 6	for i := 0; i < n; i++ {
 7		for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
 8			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
 9		}
10	}
11
12	// 再次遍历数组，找到第一个不在正确位置上的数字
13	for i := 0; i < n; i++ {
14		if nums[i] != i + 1 {
15			return i + 1
16		}
17	}
18
19	// 如果数组中的数字是从 1 到 n 的连续数字，则最小的缺失数字是 n+1
20	return n + 1
21}