缺失的第一个正数

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

 

示例 1:

输入: [1,2,0]
输出: 3
示例 2:

输入: [3,4,-1,1]
输出: 2
示例 3:

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

提示:

你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-missing-positive

前言
如果本题没有额外的时空复杂度要求,那么就很容易实现:

我们可以将数组所有的数放入哈希表,随后从 11 开始依次枚举正整数,并判断其是否在哈希表中;

我们可以从 11 开始依次枚举正整数,并遍历数组,判断其是否在数组中。

如果数组的长度为 NN,那么第一种做法的时间复杂度为 O(N)O(N),空间复杂度为 O(N)O(N);第二种做法的时间复杂度为 O(N^2)O(N
2
),空间复杂度为 O(1)O(1)。但它们都不满足题目的要求:时间复杂度为 O(N)O(N),空间复杂度为 O(1)O(1)。

「真正」满足此要求的算法是不存在的。但是我们可以退而求其次:利用给定数组中的空间来存储一些状态。也就是说,如果题目给定的数组是不可修改的,那么就不存在满足时空复杂度要求的算法;但如果我们可以修改给定的数组,那么是存在满足要求的算法的。

方法一:哈希表
对于「前言」中提到的第一种做法:

我们可以将数组所有的数放入哈希表,随后从 11 开始依次枚举正整数,并判断其是否在哈希表中。

仔细想一想,我们为什么要使用哈希表?这是因为哈希表是一个可以支持快速查找的数据结构:给定一个元素,我们可以在 O(1)O(1) 的时间查找该元素是否在哈希表中。因此,我们可以考虑将给定的数组设计成哈希表的「替代产品」。

实际上,对于一个长度为 NN 的数组,其中没有出现的最小正整数只能在 [1, N+1][1,N+1] 中。这是因为如果 [1, N][1,N] 都出现了,那么答案是 N+1N+1,否则答案是 [1, N][1,N] 中没有出现的最小正整数。这样一来,我们将所有在 [1, N][1,N] 范围内的数放入哈希表,也可以得到最终的答案。而给定的数组恰好长度为 NN,这让我们有了一种将数组设计成哈希表的思路:

我们对数组进行遍历,对于遍历到的数 xx,如果它在 [1, N][1,N] 的范围内,那么就将数组中的第 x-1x−1 个位置(注意:数组下标从 00 开始)打上「标记」。在遍历结束之后,如果所有的位置都被打上了标记,那么答案是 N+1N+1,否则答案是最小的没有打上标记的位置加 11。

那么如何设计这个「标记」呢?由于数组中的数没有任何限制,因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质:由于我们只在意 [1, N][1,N] 中的数,因此我们可以先对数组进行遍历,把不在 [1, N][1,N] 范围内的数修改成任意一个大于 NN 的数(例如 N+1N+1)。这样一来,数组中的所有数就都是正数了,因此我们就可以将「标记」表示为「负号」。算法的流程如下:

我们将数组中所有小于等于 00 的数修改为 N+1N+1;

我们遍历数组中的每一个数 xx,它可能已经被打了标记,因此原本对应的数为 |x|∣x∣,其中 |\,|∣∣ 为绝对值符号。如果 |x| \in [1, N]∣x∣∈[1,N],那么我们给数组中的第 |x| - 1∣x∣−1 个位置的数添加一个负号。注意如果它已经有负号,不需要重复添加;

在遍历完成之后,如果数组中的每一个数都是负数,那么答案是 N+1N+1,否则答案是第一个正数的位置加 11。

以下是不注重时间复杂度的算法

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        ans = sorted(nums)
        min_num = 1

        for i in ans:
            if i < min_num:
                continue
            elif i == min_num:
                min_num += 1
            else:
                return min_num
        return min_num

以下是哈希表法

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if not nums:
            return 1
        length = len(nums)
        for i in range(length):
            if nums[i] <= 0:
                nums[i] = length + 1
        for i in range(length):
            num = abs(nums[i])
            if num <= length:
                nums[num - 1] = -abs(nums[num - 1])
        for i in range(length):
            if nums[i] > 0:
                return i + 1
        return length+1
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00