「力扣」第 41 题:缺失的第一个正数(困难)

liweiwei1419 ... 2022-1-6 原地哈希
  • 原地哈希
About 8 min

# 📺 视频题解

视频讲解:B 站 (opens new window)

说明:

  • 建议倍速观看,核心思想不难,三分钟以后才进入正题,为了叙述完整所以讲得比较多;
  • 方法一和方法二都很容易想到,可以直接跳到「方法三」。

视频讲解

📺 这道题在 题解 (opens new window)B 站 (opens new window) 可以收看视频讲解,可以点击下面的视频右上角「去 bilibili 观看」,选择快速播放,获得更好的观看体验。

# 题目描述

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

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

示例 1:

输入:nums = [1,2,0]
输出:3
1
2

示例 2:

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

示例 3:

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

提示:

  • 1nums.length51051 \le nums.length \le 5 * 10^5
  • 231nums[i]2311-2^{31} \le nums[i] \le 2^{31} - 1

# 一句话题解

本题的难点在:只能使用常数级别的额外空间,在这个限制下本题的思路有一个非正式的名称:原地哈希。

# 方法一:哈希表(空间复杂度不符合要求)

  • 按照刚才我们读例子的思路,其实我们只需从最小的正整数 11 开始,依次判断 223344 直到数组的长度 NN 是否在数组中;
  • 如果当前考虑的数不在这个数组中,我们就找到了这个缺失的最小正整数;
  • 由于我们需要依次判断某一个正整数是否在这个数组里,我们可以先把这个数组中所有的元素放进哈希表。接下来再遍历的时候,就可以以 O(1)O(1) 的时间复杂度判断某个正整数是否在这个数组;
  • 由于题目要求我们只能使用常数级别的空间,而哈希表的大小与数组的长度是线性相关的,因此空间复杂度不符合题目要求。

参考代码 1

import java.util.HashSet;
import java.util.Set;

public class Solution {

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        Set<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            hashSet.add(num);
        }

        for (int i = 1; i <= len ; i++) {
            if (!hashSet.contains(i)){
                return i;
            }
        }

        return len + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

  • 时间复杂度:O(N)O(N),这里 NN 表示数组的长度。第 1 次遍历了数组,第 2 次遍历了区间 [1, len] 里的元素。
  • 空间复杂度:O(N)O(N),把 NN 个数存在哈希表里面,使用了 NN 个空间。

# 方法二:二分查找(时间复杂度不符合要求)

  • 根据刚才的分析,这个问题其实就是要我们查找一个元素,而查找一个元素,如果是在有序数组中查找,会快一些;
  • 因此我们可以将数组先排序,再使用二分查找法从最小的正整数 11 开始查找,找不到就返回这个正整数;
  • 这个思路需要先对数组排序,而排序使用的时间复杂度是 O(NlogN)O(N \log N),是不符合这个问题的时间复杂度要求。

参考代码 2

import java.util.Arrays;

public class Solution {

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);

        for (int i = 1; i <= len; i++) {
            int res = binarySearch(nums, i);
            if (res == -1) {
                return i;
            }
        }
        return len + 1;
    }

    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
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

复杂度分析

  • 时间复杂度:O(NlogN)O(N \log N),这里 NN 表示数组的长度。时间复杂度主要消耗在排序上,排序使用 O(NlogN)O(N\log N)。二分查找使用每一步使用的时间复杂度是 O(logN)O(\log N),整体上仍然是 O(NlogN)O(N \log N)
  • 空间复杂度:O(1)O(1)

说明:评论区 @pingfan108 朋友给出了排序以后不用二分的做法,可以点击 这里 (opens new window) 查看,特此表示感谢。

# 方法三:将数组视为哈希表

最早知道这个思路是在《剑指 Offe》这本书上看到的,感兴趣的朋友不妨做一下这道问题:剑指 Offer 03. 数组中重复的数字 (opens new window)。下面简要叙述:

  • 由于题目要求我们「只能使用常数级别的空间」,而要找的数一定在 [1, N + 1] 左闭右闭(这里 N 是数组的长度)这个区间里。因此,我们可以就把原始的数组当做哈希表来使用。事实上,哈希表其实本身也是一个数组
  • 我们要找的数就在 [1, N + 1] 里,最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下,我们才返回 N + 1
  • 那么,我们可以采取这样的思路:就把 11 这个数放到下标为 00 的位置, 22 这个数放到下标为 11 的位置,按照这种思路整理一遍数组。然后我们再遍历一次数组,第 11 个遇到的它的值不等于下标的那个数,就是我们要找的缺失的第一个正数。
  • 这个思想就相当于我们自己编写哈希函数,这个哈希函数的规则特别简单,那就是数值为 i 的数映射到下标为 i - 1 的位置。

我们来看一下这个算法是如何应用在示例 2 上的。

0041-14.png

动画演示:

参考代码 3

注意:理解下面代码 nums[nums[i] - 1] != nums[i] 的作用。

这里感谢用户 @rmokerone 提供 C++ 版本的代码。

说明:Python 里可以这样写 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] ,但是这里赋值有先后顺序,写成 nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i], 就会出错。建议封装成单独的函数,避免出错。

复杂度分析

  • 时间复杂度:O(N)O(N),这里 NN 是数组的长度。

说明:while 循环不会每一次都把数组里面的所有元素都看一遍。如果有一些元素在这一次的循环中被交换到了它们应该在的位置,那么在后续的遍历中,由于它们已经在正确的位置上了,代码再执行到它们的时候,就会被跳过。

最极端的一种情况是,在第 1 个位置经过这个 while 就把所有的元素都看了一遍,这个所有的元素都被放置在它们应该在的位置,那么 for 循环后面的部分的 while 的循环体都不会被执行。

平均下来,每个数只需要看一次就可以了,while 循环体被执行很多次的情况不会每次都发生。这样的复杂度分析的方法叫做均摊复杂度分析

最后再遍历了一次数组,最坏情况下要把数组里的所有的数都看一遍,因此时间复杂度是 O(N)O(N)

  • 空间复杂度:O(1)O(1)

# 同类问题

问题 题解
442. 数组中重复的数据 (opens new window) 题解 (opens new window)
448. 找到所有数组中消失的数字 (opens new window) 题解 (opens new window)
Last update: January 14, 2022 00:02
Contributors: liweiwei1419