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

2次阅读

共计 1824 个字符，预计需要花费 5 分钟才能阅读完成。

题目来源：力扣（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 落在正确的位置之后，直接跳过，遍历下一个元素。