First Missing Positive

Description

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

  • Your algorithm should run in O(n) time and uses constant extra space.

使用O(n)的时间复杂度和恒定的空间在无序数组中查找第一个缺失的正数。

Solution

此题关键在于利用数字直接寻找其位置,达到排序目的。

假设有数组[4, 3, 5, 1]

取第一个数4,检查4是否在第4个位置:,与第四个位置数字交换得到[1, 3, 5, 4]

交换后继续判断当前数字1是否在第1个位置:,则跳过。

依次判断之后得到数组[1, 5, 3, 4]。其中遇到5时因为其超过数组长度,直接跳过。

再次从第一个位置开始判断,找到第一个位置与数字不符合的地方即为缺失的数字。

 1func firstMissingPositive(nums []int) int {
 2    l := len(nums)
 3
 4    // 进行排序
 5    for i := 0; i < l; {
 6        n := nums[i]
 7
 8        if n <= 0 || n > l {
 9            // 溢出的不用管
10            i++
11        } else if i+1 != n && nums[n-1] != n {
12            // 判断当前数字是否在它应该的位置上
13            // 数字 n 应该在[n - 1]上
14            // 需要处理目标位置与当前位置数字相同,否则死循环
15            nums[i] = nums[n-1]
16            nums[n-1] = n
17            // 交换位置后,继续处理当前位置上的数字,不需要i++
18        } else {
19            // 处理下一个位置
20            i++
21        }
22    }
23
24    // 查找第一个不符合的数字
25    for i := 0; i < l; i++ {
26        if nums[i] != i+1 {
27            return i + 1
28        }
29    }
30
31    return l + 1
32}