41. 缺失的第一个正数（First Missing Positive）

频次 ★★★★ · 难度 🔴 · 高频：字节/阿里

题目

给定一个未排序的整数数组，找出其中没有出现的最小正整数。要求时间复杂度 O(n)，空间复杂度 O(1)。

示例：

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

思路

原地哈希（索引映射）：

• 长度为 n 的数组，缺失的最小正整数一定在 [1, n+1] 范围内
• 目标：让 nums[i] = i + 1（即值为 1 的放索引 0，值为 2 的放索引 1…）
• 遍历数组，将每个在 [1, n] 范围内的数放到正确位置
• 再遍历一次，第一个 nums[i] != i + 1 的位置就是答案

注意：重复元素和超出范围的数可以忽略。

代码

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

复杂度

• 时间：O(n) — 每个元素最多被交换一次到正确位置
• 空间：O(1) — 原地操作

边界条件

• 数组为空：n == 0，两个循环都不执行，直接返回 n + 1 == 1，正确（空数组缺失的最小正整数是 1）。
• 数组全是负数或 0（如 [-1,-2,0]）：第一个循环的 while 条件 nums[i] > 0 && nums[i] <= n 恒为假，不发生交换，第二个循环发现所有位置都不满足 nums[i] == i+1，第一个不满足的位置返回 i+1，即 1。
• 数组恰好是 [1,2,...,n] 的排列：第二个循环全部满足 nums[i] == i+1，返回 n+1。

变式

• 如果允许 O(n) 额外空间：可以直接用布尔数组或 HashSet 标记 [1,n] 范围内出现过的数字，再从 1 开始找第一个没出现的，思路更直观但不满足本题”O(1) 空间”的进阶要求。
• 找出所有缺失的正数（而不只是第一个）：448. 找到所有数组中消失的数字 用的是”用负号标记”而不是”交换到正确位置”，思路更简单，但只适用于”数字范围恰好是 [1,n]“这种更受限的场景。

易错点

• while 循环的三个条件缺一不可：nums[i] > 0（排除非正数）、nums[i] <= n（排除超出范围的数，这些数不可能是答案，也没有对应的存放位置）、nums[nums[i]-1] != nums[i]（避免重复值导致死循环交换）。
• 交换时要用临时变量保存 nums[nums[i]-1]，如果先赋值 nums[i] = temp 再计算 nums[nums[i]-1]，nums[i] 已经被改写，索引会算错。

面试追问

• 为什么这题能做到 O(n) 时间 O(1) 空间？关键洞察是什么？ 关键在于：长度为 n 的数组，答案必然落在 [1, n+1] 范围内（抽屉原理——如果 1..n 都出现了，答案就是 n+1；否则答案是 1..n 中缺失的那个）。这让我们可以把数组本身当作哈希表，用”值放到它该在的下标”这一操作原地建立映射，不需要额外空间。
• 每个元素最多被交换多少次，为什么总时间复杂度还是 O(n)？ 每次交换都会让至少一个元素落到它的正确位置上（nums[nums[i]-1] == nums[i]），一个元素一旦落到正确位置就不会再被移动，所以总交换次数不超过 n 次，均摊下来外层循环加交换总共是 O(n)。

关联题

• 同套路：448. 找到所有数组中消失的数字 —— “下标即哈希”的原地标记，它是无约束热身版
• 进阶：287. 寻找重复数 —— 不许改数组时转成下标成环，用 Floyd 判圈
• 易混：73. 矩阵置零 —— 同为 O(1) 标记，但那题是借首行首列当标记位
• 知识点：鸽巢原理——答案必在 [1, n+1] 内，这是所有 O(1) 空间解法的前提