leetcode 41. 缺失的第一个正数 - python

https://leetcode-cn.com/probl...

题目概括

给定正数数组 nums,返回数组中没有的最小的一个正整数。

要求:时间复杂度 O(n),空间复杂度 O(1)

解法

这个题目的巧妙之处在于利用了输入的数组做标记,这样省去了使用额外空间,从而实现了 O(1) 的空间复杂度。

关键点是:设数组长度为 n,那么答案一定在 [1, n+1] 之中。这是显而易见,因为 nums 里只有 n 个数,不可能出现 [1, n+1] 里的所有数字。

如果想实现 O(n) 的时间复杂度,只能遍历,不能排序,这里的方法是

处理特殊情况,如果 1 不再 nums 里,答案自然是 1。否则:

首先除掉数组中 [1, n+1] 以外的数,因为他们根本不会影响结果,干脆把这些数都写成 1。

然后,nums 里只有正数了,而且值在 [1, n] 之内。我们遍历数组,对于数组里每个数字,令 nums 对应的第这个位置的数变成负数。就把所有数的位置标记出来了,相当于用了一个 桶排序算法

然后再遍历一下,第一个不是负数的位置就是缺失的数了。

这里需要特殊处理 n,因为 n 会越界,干脆用位置 0 代表 n,或者也可以把所有数统一减一。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if 1 not in nums:
            return 1
        n = len(nums)
        for i in range(n):
            if nums[i] > n or nums[i] <= 0:
                nums[i] = 1
        for i in range(n):
            a = abs(nums[i])
            if a == n:
                nums[0] = -abs(nums[0])
            else:
                nums[a] = -abs(nums[a])
        for i in range(2, n):
            if nums[i] > 0: return i
        return n if nums[0] > 0 else n+1

欢迎来我的博客: https://codeplot.top/

我的博客刷题分类: https://codeplot.top/categori...

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章