跳到主要内容

41. 缺失的第一个正数

题目描述​

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

解题思路​

第一步：理解问题本质​

题目要求找"没有出现的最小正整数"，答案一定是 1, 2, 3, ... 中的某一个。

关键观察：对于一个长度为 n 的数组，缺失的第一个正整数一定在范围 [1, n+1] 内。

为什么？假设数组 nums 长度为 n，它最多能"覆盖"1 到 n 这 n 个正整数。如果 1 到 n 全部出现，那么答案是 n+1；否则答案是 1 到 n 之间某个缺失的数。无论如何，答案不会超过 n+1。

这个观察非常重要，它告诉我们：只需要关心 1 到 n 之间的数，超出范围的数（负数、0、大于 n 的数）对答案没有贡献。

第二步：暴力解法​

最直接的思路是用一个哈希集合记录数组中出现了哪些数，然后从 1 开始往上找，第一个不在集合中的就是答案。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        num_set = set(nums)
        i = 1
        while i in num_set:
            i += 1
        return i
  • 时间复杂度：O(n)（建集合 O(n)，查找最多 O(n)）
  • 空间复杂度：O(n)（需要额外的哈希集合）

为什么不够好：时间复杂度已经满足要求，但空间复杂度是 O(n)，而题目明确要求只使用常数级别额外空间，因此这个解法不符合题目要求。

第三步：优化解法（预处理数组）​

在哈希集合方法的基础上，能否不用额外的集合？

注意到数组本身就有 n 个存储槽位，而我们需要记录的信息也恰好是 1 到 n 中哪些数出现了。如果能把数组下标当作哈希表的 key，把数组的值当作"是否存在"的标记，就不需要额外空间了。

这引出了"原地哈希"的核心思路。

第四步：最优解法（原地哈希）​

核心思想：将数值 i 放到下标 i-1 的位置。整理完成后，第一个不满足 nums[i] == i+1 的位置 i，对应的答案就是 i+1。

换句话说，我们希望整理后的数组满足：

  • 下标 0 的位置存放数值 1
  • 下标 1 的位置存放数值 2
  • 下标 2 的位置存放数值 3
  • ……

整理规则：遍历数组，对于每个位置 i，如果 nums[i] 满足 1 <= nums[i] <= n，就把它"送回家"——交换到下标 nums[i]-1 的位置。

为什么用 while 而不是 if？

交换是把两个位置的数互换。交换之后，原来在 nums[nums[i]-1] 位置的数被换到了 i，这个新来的数可能同样需要被送去它的正确位置。所以要持续检查和交换，直到当前位置的数不需要移动为止——这就需要 while 循环。

为什么终止条件是 nums[i] != nums[nums[i]-1] 而不是 nums[i]-1 != i？

如果 nums[i]-1 != i，说明当前的数还没到达正确位置，应该继续交换。但是，如果目标位置 nums[i]-1 上已经有了正确的数（即 nums[nums[i]-1] == nums[i]），那再交换也没有意义，而且会造成死循环（两个相同的数来回互换）。

因此判断条件要同时满足：

  1. nums[i] 在有效范围内：1 <= nums[i] <= n
  2. 当前数还没到正确位置，且目标位置上的数不是正确的值：nums[i] != nums[nums[i]-1]
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        size = len(nums)
        # 第一步：整理数组，把每个数放到它应该在的位置
        for i in range(size):
            # nums[i] 应该放到下标 nums[i]-1 处
            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        # 第二步：找第一个不满足 nums[i]==i+1 的位置
        for i in range(size):
            if nums[i] != i + 1:
                return i + 1
        return size + 1

完整代码实现​

from typing import List

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

        # 第一步：原地哈希，将每个合法正整数 v 放到下标 v-1 的位置
        for i in range(size):
            # 持续交换，直到 nums[i] 到达正确位置，或目标位置已有正确的数
            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]

        # 第二步：顺序扫描，找第一个"位置与值不匹配"的下标
        for i in range(size):
            if nums[i] != i + 1:
                return i + 1

        # 第三步：如果 1~n 全部存在，答案是 n+1
        return size + 1

示例推演​

以 nums = [3, 4, -1, 1]（n=4）为例，逐步展示原地哈希的整理过程。

目标状态：整理后希望 nums = [1, 2, 3, 4]，即下标 i 处存放 i+1。

第一步：整理数组

初始状态：[3, 4, -1, 1]，下标分别为 0, 1, 2, 3

i = 0，nums[0] = 3

  • 3 在范围 [1,4] 内，且 nums[0]=3 != nums[2]=−1，需要交换
  • 把 3 送到下标 3-1=2 的位置：交换 nums[0] 和 nums[2]
  • 数组变为：[-1, 4, 3, 1]

此时 nums[0] = -1，不在范围 [1,4] 内，while 结束，继续下一个 i。

i = 1，nums[1] = 4

  • 4 在范围 [1,4] 内，且 nums[1]=4 != nums[3]=1，需要交换
  • 把 4 送到下标 4-1=3 的位置：交换 nums[1] 和 nums[3]
  • 数组变为：[-1, 1, 3, 4]

此时 nums[1] = 1，在范围 [1,4] 内，且 nums[1]=1 != nums[0]=-1，需要继续交换：

  • 把 1 送到下标 1-1=0 的位置：交换 nums[1] 和 nums[0]
  • 数组变为：[1, -1, 3, 4]

此时 nums[1] = -1，不在范围 [1,4] 内，while 结束。

i = 2，nums[2] = 3

  • 3 在范围 [1,4] 内，且 nums[2]=3 == nums[2]=3（目标位置已经是正确的数），while 结束。

i = 3，nums[3] = 4

  • 4 在范围 [1,4] 内，且 nums[3]=4 == nums[3]=4（目标位置已经是正确的数），while 结束。

整理完成，数组为：[1, -1, 3, 4]

第二步：找第一个不匹配的位置

下标 inums[i]期望值 i+1是否匹配
011匹配
1-12不匹配

第一个不匹配的位置是 i=1，答案为 i+1 = 2。

验证：原数组 [3, 4, -1, 1] 中，正整数有 1, 3, 4，缺少 2，答案正确。

再以 nums = [1, 2, 0]（n=3）为例验证边界情况：

整理过程：

  • i=0：nums[0]=1，目标位置 nums[0] 已正确，跳过
  • i=1：nums[1]=2，目标位置 nums[1] 已正确，跳过
  • i=2：nums[2]=0，不在范围 [1,3] 内，跳过

整理后数组：[1, 2, 0]

扫描：

  • i=0：nums[0]=1，匹配
  • i=1：nums[1]=2，匹配
  • i=2：nums[2]=0，期望 3，不匹配，返回 3

答案为 3，正确。

复杂度分析​

解法时间复杂度空间复杂度说明
哈希集合O(n)O(n)需要额外集合，不满足空间要求
原地哈希O(n)O(1)每个元素最多被交换一次，时间均摊 O(n)

关于原地哈希时间复杂度的说明：虽然代码中有嵌套的 while 循环，但每次交换都会将至少一个数放到正确位置，且每个位置最多被放置一次，所以总交换次数不超过 n 次，整体时间复杂度仍为 O(n)。

易错点总结​

  1. 忘用 while，错用 if：交换后新来到当前位置的数也可能需要继续交换，用 if 只交换一次会遗漏这种情况，导致整理不完全。

  2. 终止条件写成 nums[i]-1 != i：没有处理"目标位置已有正确的数"的情况，当数组中有重复数字时（如 [1,1]），会导致两个相同的数来回互换，陷入死循环。

  3. 整理后忘记处理"全部匹配"的情况：如果 1 到 n 全部出现，两层循环都不会提前返回，此时答案是 n+1，不要忘记最后的 return size + 1。

  4. 答案范围理解错误：答案一定在 [1, n+1] 内，超出这个范围的数（负数、0、大于 n 的数）直接忽略，不影响答案。

扩展思考​

相关题目：

  • LeetCode 268：丢失的数字（数组包含 0 到 n，找缺失的那个）
  • LeetCode 448：找到所有数组中消失的数字（找出所有缺失的正整数）
  • LeetCode 645：错误的集合（找到重复的数和缺失的数）

算法本质：原地哈希（In-place Hashing）是一种将数组自身当作哈希表使用的技巧。当需要记录的信息（如"某个值是否出现"）与数组下标天然对应时，就可以省去额外的哈希表，将空间复杂度从 O(n) 降到 O(1)。这种技巧在"数组中的数值范围与下标范围相近"的场景下特别有效。

加载评论中...