算法 - 缺失的第一个正数

Posted on

1. 题目

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

要求：时间复杂度 O(n)，并且只使用常数级别额外空间。

示例:

1
2
3
4
5
6
输入: nums = [3,4,-1,1]
输出: 2
解释: 缺失的最小正整数是 2。

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

2. 解题思路

关键结论：长度为 n 的数组，答案一定落在 [1, n + 1] 区间内（最理想情况数组恰好是 1..n，则答案为 n+1）。

2.1 原地哈希（把 i 放到位置 i-1）

目标：让数组「归位」——值 x（1 ≤ x ≤ n）应放到下标 x - 1。

  • 遍历数组，对每个 nums[i]，只要它在 [1, n] 且「它该去的位置上的值还不等于它」，就交换过去（循环，因为换回来的值可能也需归位）。

  • 归位后再扫一遍，第一个 nums[i] !== i + 1 的位置，i + 1 就是缺失的最小正数。

  • 时间复杂度：O(n)（每个元素最多被交换归位一次），空间复杂度：O(1)。

2.2 为什么不能用哈希集合？

可以用 Set 存所有正数再从 1 开始找，满足 O(n) 时间，但空间 O(n)，不满足「常数空间」的进阶要求——面试先讲 Set 思路，再优化到原地哈希。

3. TypeScript 实现

3.1 原地哈希（交换法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function firstMissingPositive(nums: number[]): number {
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        // 只要 nums[i] 在 [1,n] 且没归位，就把它换到 nums[i]-1 处
        while (
            nums[i] > 0 &&
            nums[i] <= n &&
            nums[nums[i] - 1] !== nums[i]
        ) {
            const target = nums[i] - 1;
            [nums[i], nums[target]] = [nums[target], nums[i]];
        }
    }

    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }

    return n + 1; // 1..n 全在，答案为 n+1
}

console.log(firstMissingPositive([3, 4, -1, 1])); // 2

坑点：解构交换 [nums[i], nums[target]] = [...] 中 target 必须先算好；若写成 nums[nums[i]-1] 内联，赋值左侧求值顺序会导致索引错乱。

3.2 标记法（取负，等价思路）

先把所有 ≤0 的数替换成 n+1（移出有效区），再对每个值的绝对值 v（1≤v≤n）把 nums[v-1] 取负作为「出现过」标记，最后第一个非负下标 +1 即答案。同样 O(n) 时间 O(1) 空间。

4. 面试延伸

  • 原地哈希 vs 排序：排序 O(n log n)，原地哈希利用「答案范围有界」把空间压到 O(1)，是本题精髓。
  • 变形题「数组中重复的数字 / 找丢失的数字」都能复用「下标当哈希表」这一模式。
  • 追问：为什么 while 而不是 if？因为一次交换换来的新值可能也需要归位，必须持续下沉。

难度：困难 | LeetCode 41 | 原地哈希经典