LeetCode 41. 缺失的第一个正数 | Python

大梦三千秋 2020/6/28 13:26:25

41. 缺失的第一个正数 题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/first-missing-positive 题目 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3示例 2: 输入: [3,4,-1,1] 输出: 2示例 3: 输入: [7,8,…

41. 缺失的第一个正数


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

题目


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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题思路


思路:交换

因为题目中要求【算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间】。

如果没有这样的限制,那么可以使用哈希表的方法:

  • 将数组元素存入哈希表,从头遍历,判断是否在哈希表中(但是这种方法的时间复杂度虽然为 O(n),但是空间复杂度也为 O(n),不符合前提)

但是仔细审题之后,会发现,因为题目所给的数组是没有经过排序的。那么如果将所给的数组进行恢复,到时候遍历查看即能找到缺失的正数。

在给定的数组中,我们需要找的整数一定是落在 [1, n+1] (n 表示数组长度) 这个区间。但是 n + 1 并不用求,因为当前面 n 个数不满足时,要求的自然就是 n+1。

我们看示例 2:

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

在这个例子当中,我们将其恢复,那么数组最终是这样的:[1, -1, 3, 4],这样我们就可以发现,数组中缺失的就是就是数字 2。

那么现在的问题即是如何进行恢复。大致的思路是这样的:将 1 放到索引为 0 的位置上,2 放到索引为 1 的位置上,依次类推。

也即是说,设当前遍历的元素为 a,也就是说 a = nums[i],如果 a 落在 [1, n],根据上面的思路,那么 a 应该落在索引为 a-1 的位置。这个时候,交换 nums[i]nums[a-1],那么 a 就会落在正确的位置。但是这里交换位置后的元素如果还在 [1, n] 的范围内,还需要继续进行交换操作,直到 a 不再落在 [1, n]。具体的过程如下图所示:

图片描述

在这里需要注意防止陷入死循环。如果 a 本来就在正确的位置上时,上面的方法将会一直交换下去。所以在这里要注意,当元素出现在正确的位置上时,不需要交换跳过,直接下一个元素。

具体的代码实现如下。

代码实现


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        length = len(nums)

        for i in range(length):
            # 这里判断元素是否落在 [1, n],判断是否落在正确的位置
            # 注意:防止进入死循环,当元素刚好落在正确位置,直接跳过,判断下个元素
            while 1 <= nums[i] <= length and nums[i] != nums[nums[i] - 1]:
                # 交换
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        
        # 将数组的元素恢复到正确的位置后,
        # 再次遍历,当某个元素不在正确的位置时,就是要找的第一个缺失的正数,直接返回
        for i in range(length):
            if nums[i] != i + 1:
                return i + 1
        # 如果元素都在正确位置,那么缺失的就是 n+1(length+1)
        return length + 1

实现结果


实现结果

总结


  • 因为给定的数组并没有排序,而且我们知道,要求的缺失的正数,那么将数组恢复到正确的位置,那么遍历的时候,就知道哪个正数不在正确的位置,也就是缺失的正数
  • 根据题意,我们知道,要找的正数一定是落在 [1, n+1](n 表示数组长度)这个区间的。但是 n+1 并不需要求,因为前面如果都在正确位置,那么缺失的就是 n+1。
  • 如何进行恢复:
    • 根据上面所述,大致的思路即是:1 应该落在索引为 0 的位置,2 应该落在索引为 1 的位置,以此类推。
    • 假设当前元素为 a(令 a=nums[i],仅为更容易理解),如果 a 落在 [1, n] 这个区间,那么 a 应该落在索引为 a-1 的位置。那么交换位置,也就是 nums[a-1] 与 a 交换(将 a = nums[i] 代入,即是 nums[nums[i]-1] 与 nums[i] 交换),交换之后 a 可能还落在 [1, n],直到 a 不再这个区间内。
    • 这里需要注意:不要陷入死循环。上面的前提是 a 落在 [1, n] 区间,要将 a 放到正确的位置,下面就是需要注意的地方,如果 a 本来就落在正确的位置,这个交换就会无限循环下去。所以,当 a 落在正确的位置之后,直接跳过,遍历下一个元素。

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[LeetCode 41. 缺失的第一个正数 | Python]http://www.zyiz.net/tech/detail-141258.html

上一篇:Python探索之旅 | 第一部分第一课:Python是什么?

下一篇:Python探索之旅 | 第一部分第一课:Python是什么?

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程