缺失的第一个正数

阅读要点

• 缺失的第一个正数答案只可能出现在 1 到 n+1 之间（抽屉原理）。
• 解法一使用哈希表标记数组中出现的数字，然后遍历 1 到 n 查找缺失值。
• 解法二通过原地交换将每个值 v 放到索引 v-1 处，空间复杂度降为 O(1)。
• 交换时需注意避免死循环，条件为 nums[j] 在 [1, n] 且不与目标位置值相等。

开始写作

41. 缺失的第一个正数 - 力扣（LeetCode）

解法一 标记法

思路

本题虽然被标记为「困难」，但代码实现其实非常简单。难点主要在于思路，需要运用一些数学思想。

本解法运用了抽屉原理：答案只会出现在 1 到 n+1 之间。原因：考虑极端情况，如果 nums 包含了从 1 到 n 的所有数，那么答案就是 n+1；否则，缺失的数中最小的那个就是答案。

例如，对于数组 [3, 4, -1, 1]，长度为 4，答案应该在 1 到 5 之间。实际缺失的最小正数是 2。

因此，我们可以用一个字典来标记数组中包含的数，然后遍历 1 到 n，寻找第一个不存在的数。

代码

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        mp = collections.defaultdict(int)
        for i in range(len(nums)):
            mp[nums[i]] = i
        for i in range(1, len(nums) + 1):
            if i not in mp:
                return i
        return len(nums) + 1

复杂度分析：

• 时间复杂度：O(n)，遍历数组两次。
• 空间复杂度：O(n)，使用了哈希表存储。

解法二 原地交换法

思路

解法一的思路直观，但空间复杂度为 O(n)。为了优化空间，我们可以利用数组本身作为哈希表。具体做法是：遍历数组，对于每个值 v，如果它在 1 到 n 范围内，就将其交换到索引 v-1 的位置。这样，经过一轮交换后，所有在范围内的数都处于正确位置。然后再次遍历，第一个位置与值不匹配的索引 i 对应的缺失值就是 i+1。

例如，对于数组 [3, 4, -1, 1]，交换过程如下：

• 初始：[3, 4, -1, 1]
• i=0: 3 应到索引 2，交换后 [-1, 4, 3, 1]
• i=0: -1 不在范围内，跳过
• i=1: 4 应到索引 3，交换后 [-1, 1, 3, 4]
• i=1: 1 应到索引 0，交换后 [1, -1, 3, 4]
• i=1: -1 不在范围内，跳过
• i=2: 3 已在正确位置，跳过
• i=3: 4 已在正确位置，跳过
• 最终数组：[1, -1, 3, 4]，第一个不匹配的位置是索引 1，值为 -1，缺失值为 2。

代码

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            j = i
            while 1 <= nums[j] <= len(nums) and nums[j] != nums[nums[j] - 1]:
                nums[nums[j] - 1], nums[j] = nums[j], nums[nums[j] - 1]
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1

复杂度分析：

• 时间复杂度：O(n)，每个元素最多被交换两次。
• 空间复杂度：O(1)，原地交换，只使用了常数额外空间。

收获

• 解法一（哈希表标记）时间复杂度 O(n)，空间复杂度 O(n)，易于理解。
• 解法二（原地交换）时间复杂度 O(n)，空间复杂度 O(1)，更优但实现稍复杂。
• 两种方法都利用了「答案在 1~n+1 之间」这一关键性质。
• 原地交换法需要注意循环条件，避免死循环。