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)的时间复杂度和O(1)的空间在无序数组中查找第一个缺失的正数。

Solution

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

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func firstMissingPositive(nums []int) int {
    l := len(nums)

    // 进行排序
    for i := 0; i < l; {
        n := nums[i]

        if n <= 0 || n > l {
            // 溢出的不用管
            i++
        } else if i+1 != n && nums[n-1] != n {
            // 判断当前数字是否在它应该的位置上
            // 数字 n 应该在[n - 1]上
            // 需要处理目标位置与当前位置数字相同，否则死循环
            nums[i] = nums[n-1]
            nums[n-1] = n
            // 交换位置后，继续处理当前位置上的数字，不需要i++
        } else {
            // 处理下一个位置
            i++
        }
    }

    // 查找第一个不符合的数字
    for i := 0; i < l; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }

    return l + 1
}