乐趣区

LeetCode-41-缺失的第一个正数-Python

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 落在正确的位置之后,直接跳过,遍历下一个元素。

文章原创,觉得写得还可以,欢迎关注点赞。微信公众号《书所集录》同步更新,同样欢迎关注点赞。

退出移动版