LeetCode-41.缺失的第一个正数

数组#

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

1
输入：nums = [1,2,0]
2
输出：3
3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

1
输入：nums = [3,4,-1,1]
2
输出：2
3
解释：1 在数组中，但 2 没有。

示例 3：

1
输入：nums = [7,8,9,11,12]
2
输出：1
3
解释：最小的正数 1 没有出现。

正确的解法

🤔，感觉很神奇

1
func firstMissingPositive(nums []int) int {
2
    n := len(nums)
3
    for i := range n {
4
        for nums[i] > 0 && nums[i] < n && nums[nums[i]-1] != nums[i] {
5
            nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
6
        }
7
    }
8

9
    for i := range n {
10
        if nums[i] != i+1 {
11
            return i+1
12
        }
13
    }
14
    return n+1
15
}

自己的解法(哈希)

写了我一节课提交了6次终于过了，感觉不是很难，但就是写不出来…

虽然耗时也挺高10ms，但终究还是写出来，毕竟也算是困难题

好吧，其实不完全满足，时间复杂度为 O(nlogn)，空间复杂度为 O(n)，算做出来一道中等题吧

1
func firstMissingPositive(nums []int) int {
2
    sort.Ints(nums)
3
    count := 0
4
    skip := 0
5
    m := []int{}
6

7
    for _, j := range nums {
8
        if j > 0 {
9
            m = append(m, j)
10
            count++
11
        }
12
    }
13

14
    for i := 0; i < count; i++ {
15
        if i > 0 && m[i] == m[i-1] {
16
            skip++
17
            if i == count-1 {
18
                return m[i]+1
19
            }
20
            continue
21
        }
22

23
        if m[i] != i - skip + 1 {
24
            return i - skip + 1
25
        }
26

27
        if i == count-1 {
28
            return m[i]+1
29
        }
30
    }
31

32
    return 1
33
}