输入#

未排序的整数数组 nums

输出#

没有出现的最小正整数

约束条件#

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

进阶约束#

实现时间复杂度 $O(n)$ 且空间复杂度 $O(1)$ 的解法。

示例1#

1
输入：nums = [1,2,0]
2
输出：3
3
解释：范围 [1,2] 中的数字都在数组中，因此缺失的最小正整数是 3。

示例2#

1
输入：nums = [3,4,-1,1]
2
输出：2
3
解释：1 在数组中，但 2 缺失，因此答案是 2。

示例3#

1
输入：nums = [7,8,9,11,12]
2
输出：1
3
解释：最小的正整数 1 缺失，因此答案是 1。

从暴力枚举出发#

最朴素的想法：从 $1$ 开始逐个检查每个正整数是否在数组中：

1
class Solution:
2
    def firstMissingPositive(self, nums: List[int]) -> int:
3
        s = set(nums)
4
        x = 1
5
        while x in s:
6
            x += 1
7
        return x

• 时间复杂度：$O(n)$（建集合 $O(n)$，检查最多 $n+1$ 次，每次 $O(1)$）
• 空间复杂度：$O(n)$（需要一个哈希集合）

虽然时间复杂度已是最优，但空间复杂度为 $O(n)$，不满足进阶要求。有没有办法把空间降到 $O(1)$？

瓶颈分析：暴力法额外建了一个哈希集合来支持快速查找。如果能原地利用数组本身作为”哈希表”，就不需要额外空间了。

原地哈希：让数组自己做”集合”#

关键的洞察是：数组的下标天然就是连续的整数 $0, 1, 2, \dots, n-1$。如果我们能让数组满足 nums[i] = i + 1（即下标 i 处存放值 i+1），那么数组本身就隐含了一个”集合”——要判断 $x$ 是否出现，只需要看 nums[x-1] 是否等于 $x$。

🧠 直觉理解：想象你在整理一排有编号的储物柜。你有一堆写着号码的包裹，你希望每个包裹 x 被放进编号为 x 的柜子里。如果你按照这个规则逐个整理包裹，那么最终”柜子是空的”或”柜子里放的号码不对”的位置，就告诉你哪个正整数缺席了。

具体来说，分两步走：

第一步：重新摆放（交换）

遍历数组，对于每个位置 i，如果 nums[i] 在 $[1, n]$ 范围内，并且它不在”正确的”位置上（即 nums[i] != nums[nums[i] - 1]），就把它和它”该去的位置”上的元素交换。重复这个过程直到当前位置无法再交换为止。

这里用 while 而不是 if 很关键——交换过来的新元素可能也在 $[1, n]$ 范围内，需要继续为它寻找正确位置：

1
for i in range(n):
2
    while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
3
        nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

第二步：寻找缺失

交换完成后，再遍历一次数组。第一个不满足 nums[i] == i + 1 的位置就对应着缺失的正整数：

1
for i in range(n):
2
    if nums[i] != i + 1:
3
        return i + 1
4
return n + 1

复杂度#

• 时间复杂度：$O(n)$。虽然内层有 while 循环，但每个数最多被交换一次到正确位置，总交换次数不超过 $n$ 次。
• 空间复杂度：$O(1)$。只使用了常数个临时变量，在原地修改数组。

💡 为什么时间复杂度不是 $O(n^2)$？ 外层循环 $n$ 次，内层的 while 看似可以多轮交换，但每次交换至少让一个数去到它的最终位置。每个数一旦”落户”就不会再被移动（因为后续 nums[i] != nums[nums[i]-1] 条件不成立）。因此总交换操作 ≤ $n$ 次，整个算法仍是线性的。这种分析方法叫做均摊分析。

最终代码（交换法）#

1
class Solution:
2
    def firstMissingPositive(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        for i in range(n):
5
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
6
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
7
        for i in range(n):
8
            if nums[i] != i + 1:
9
                return i + 1
10
        return n + 1

逐行解读：

1. n = len(nums)：数组长度。答案的范围锁定在 $[1, n+1]$。
2. 外层循环 for i in range(n)：遍历每个位置，尝试让该位置存放正确的数。
3. 交换条件 while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]：
   • 1 <= nums[i] <= n：只关心 $[1, n]$ 范围内的数，非正数和大于 $n$ 的数可以留在原地
   • nums[i] != nums[nums[i] - 1]：当前数不在它该在的位置上（避免重复交换导致死循环）
4. 交换：nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]——Python 的元组解包一次性完成交换，不需要临时变量
5. 第二遍扫描：第一个 nums[i] != i + 1 的位置，说明 i+1 缺失，直接返回
6. 兜底 return n + 1：所有位置都正确，说明 $[1, n]$ 全部出现，返回 $n+1$

⚠️ 交换语句的顺序要留意：nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] 是正确的。如果写成 nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]，Python 会先计算右侧，再从左到右赋值——这时 nums[i] 先被修改，后续 nums[nums[i] - 1] 中的 nums[i] 已经变了，导致赋值到错误的位置。所以务必把 nums[nums[i] - 1] 放在赋值语句的左侧第一位。