2021-07-12：缺失的第一个正数。给你一个未排序的整数数组

原创

福大大架构师每日一题

修改于 2021-07-13 11:25:32

4090

2021-07-12：缺失的第一个正数。给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。比如3,4,5，输出1。比如1,2,3,4,0，输出5。

福大大答案2021-07-12：

左边是有效区，右边是垃圾区。

1.遍历的当前数字是有效区最右位置的数字+1，进入有效区，有校区右扩。

2.小于等于0，进入垃圾区，垃圾区左扩。

3.大于N，进入垃圾区，垃圾区左扩。

4.数字跟数字减1位置的数字一样，进入垃圾区，垃圾区左扩。

5.剩余情况，遍历的当前数字跟数字减1位置的数字不一样，两数交换。然后继续盯着当前位置。

时间复杂度：O(N)。

空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr := []int{1, 3, 5, 7, 9, 2}
    ret := firstMissingPositive(arr)
    fmt.Println(ret)
}

func firstMissingPositive(arr []int) int {
    // l是盯着的位置
    // 0 ~ L-1有效区
    L := 0
    R := len(arr)
    for L != R {
        if arr[L] == L+1 {
            L++
        } else if arr[L] <= L || arr[L] > R || arr[arr[L]-1] == arr[L] { // 垃圾的情况
            R--
            arr[L], arr[R] = arr[R], arr[L]
        } else {
            arr[L], arr[arr[L]-1] = arr[arr[L]-1], arr[L]
        }
    }
    return L + 1
}

执行结果如下：