41. 缺失的第一个正数

题目描述

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

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

输入输出

1
2
3
4
5
6
7
8
输入：nums = [1,2,0]
输出：3

输入：nums = [3,4,-1,1]
输出：2

输入：nums = [7,8,9,11,12]
输出：1

基本思路

方法一：直接用哈希表保存 不存在即返回 时复O(n)空复O(n) 不符合要求

方法二：原地哈希 有些类似剑指 Offer 03. 数组中重复的数字

关键在这句nums[nums[i] - 1] != nums[i] 将数组自身作为哈希表 3 4 -1 1 -> 1 -1 3 4

java实现

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
33
34
35
36
37
38
39
40
41
42
43
// 方法一
class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        Set<Integer> set = new HashSet<Integer>();
        for(int num:nums){
            set.add(num);
        }
        for(int i = 1; i <= len; i++){
            if(!set.contains(i)){
                return i;
            }
        }
        return len + 1;
    }
}

// 方法二
class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        // 3 4 -1 1
        // 1 -1 3 4
        for(int i = 0; i < len; i++){
            while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]){
                // i=0 nums[i]=3 nums[nums[i]-1]=-1
                swap(nums, nums[i]-1, i);
            }
        }
        for(int i = 0; i < len; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return len + 1;
    }

    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}