Hot 100 --- 缺失的第一个正数

本文概览：本文以LeetCode经典题目"缺失的第一个正数"为例，从暴力解法入手，逐一分析哈希表和排序两种常见优化思路为何不满足 O(n) 时间 + O(1) 空间的要求，再引出原地哈希解法，系统讲解如何利用数组本身作为哈希表，将元素放到正确的位置上

一、题目

缺失的第一个正数题目

二、题目分析

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

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

核心难点：不是求出答案本身难，而是同时满足 O(n) 时间和 O(1) 空间这两个约束条件难

思路概览

Java实现代码如下

public int firstMissingPositive(int[] nums) {
    // 1. 原地hash，让nums[i]去到nums[nums[i]-1]，如果nums[3]=5，让5去到nums[4]
    int n = nums.length;
    // 交换位置
    for (int i = 0; i < n; i++) {
        // 如果nums[i]在1~n之间，并且不等于nums[nums[i]-1]，就交换位置，避免重复元素无限交换
        while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
        }
    }
    // 遍历得到最小正整数
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    // 如果都在1~n之间，就返回n+1，比如[1,2,3]，返回4
    return n + 1;
}

思路简要说明

原地哈希：利用数组本身作为哈希表，让值 v（1 ≤ v ≤ n）放到索引 v-1 的位置上
交换归位：遍历数组，如果 nums[i] 在 1~n 之间且不在正确位置，就把它和 nums[nums[i]-1] 位置的元素交换
查找结果：交换完毕后，第一个 nums[i] != i+1 的位置，i+1 就是缺失的最小正整数

三、思路详解

暴力解法入手

最自然的想法是：从 1 开始，依次检查每个正整数是否在数组中存在。检查 1 是否在，检查 2 是否在，直到找到第一个不在的

但问题是：每次检查一个数是否存在，都要遍历整个数组，而且每次都没有记住之前遍历过什么数，所以每次都要重新遍历

时间复杂度：O(n²)，最坏情况下要检查 1 到 n+1，每次都要遍历数组
核心瓶颈：没有记住已经遍历过的数，导致重复扫描

两种常见优化思路为何都不可行

题目要求 O(n) 时间 + O(1) 空间，我们来看看两种最常见的优化思路

思路一：哈希表

把数组中的每个数存入哈希表，然后从 1 开始依次查询是否在哈希表中

时间复杂度：O(n)，满足要求
空间复杂度：O(n)，哈希表需要存储所有元素，不满足 O(1) 空间的要求

思路二：先排序再遍历

将数组排序后，从左往右找到第一个不连续的正整数

空间复杂度：O(1)（如果是原地排序），满足要求
时间复杂度：排序至少 O(n log n)，不满足 O(n) 时间的要求

两种常见思路都失败了：空间换时间不行（哈希表空间超了），先排序让数组有序也不行（排序时间超了）。需要想另一种办法

原地哈希解法

关键观察一：答案的范围

缺失的第一个正整数，本质上就是从 1 开始的正整数序列中第一个断层的位置

什么意思？如果数组中包含的正整数是连续的，比如 1, 2, 3 都在，那缺失的最小正整数就是 4；但如果从某个位置开始断了，比如 1 在、2 不在，那 2 就是缺失的最小正整数，后面的数再大也没用

所以关键就是：从 1 开始往右看，第一个不连续的位置就是答案

那这个答案的范围是什么？考虑一个长度为 n 的数组，如果从 1 到 n 全部连续出现，那答案就是 n+1（断层在 n+1 的位置）；否则，断层一定出现在 1 到 n 之间。因为数组只有 n 个位置，最多容纳 n 个不同的正整数，所以不可能出现 1 到 n 全部存在、但缺失的最小正整数却大于 n+1 的情况

举个例子：

nums = [1, 2, 3]，n = 3，1→2→3 连续，断层在 4 = n+1
nums = [3, 4, -1, 1]，n = 4，1 在、2 不在，断层在 2，≤ n
nums = [7, 8, 9, 11]，n = 4，1 就不在，断层在 1，≤ n

所以结论是：缺失的最小正整数一定在 [1, n+1] 之间。大于 n 的数和小于等于 0 的数对结果没有影响，我们只需要关注 1 到 n 这些数

关键观察二：如何快速找到断层

既然答案一定在 1 到 n+1 之间，那问题就变成了：如何快速判断 1, 2, 3, ..., n 中哪个数不在数组中？

如果数组是有序的，直接从左往右扫一遍就能找到断层。但排序需要 O(n log n)，不满足时间要求

换个角度想：我们不需要让数组完全有序，只需要让每个数"各就各位"就行了。什么叫各就各位？就是让值 v 出现在索引 v-1 的位置上：

1 2	索引： 0 1 2 3 ... 对应值：1 2 3 4 ...

如果把数组变成这种一一对应的关系，那我们只需要从左往右看，第一个不满足 nums[i] == i+1 的位置，i+1 就是断层对应的缺失正整数

举个例子：nums = [3, 4, -1, 1]

归位前：

1 2	索引： 0 1 2 3 值： 3 4 -1 1

归位后（让每个值去到对应的索引位置）：

1 2	索引： 0 1 2 3 值： 1 -1 3 4

现在从左往右看：nums[0]=1 符合，nums[1]=-1 ≠ 2，断层！缺失的最小正整数就是 2

这就是原地哈希的核心思想：不创建新数组，而是把原数组本身当作哈希表，通过交换让每个值归位，然后扫描一遍就能找到断层

原地哈希的具体实现

既然只允许使用常数级别额外空间，我们无法创建新数组，但可以把原数组本身当作哈希表，通过交换让每个值归位

我们的目标是：让值 v（1 ≤ v ≤ n）放到索引 v-1 的位置上。即：

索引 0 对应值 1
索引 1 对应值 2
索引 2 对应值 3
...
索引 n-1 对应值 n

这样，交换完毕后，如果 nums[i] != i+1，就说明 i+1 这个正整数缺失了

如何把元素放到正确位置？

遍历数组，如果 nums[i] 在 1~n 之间，且不在正确位置（nums[i] != nums[nums[i]-1]），就把 nums[i] 和 nums[nums[i]-1] 位置的元素交换。交换后，nums[i] 位置上换来了一个新的值，继续判断这个新值是否也需要归位，直到当前位置的值不需要交换为止

为什么要用 nums[i] != nums[nums[i]-1] 而不是 nums[i] != i+1 作为交换条件？

因为数组中可能有重复元素。如果用 nums[i] != i+1 判断，当 nums[i] 和 nums[nums[i]-1] 的值相同时（比如都是 3），交换后两个位置的值不变，会陷入无限循环

而 nums[i] != nums[nums[i]-1] 的判断条件可以避免这个问题：当两个位置的值相同时，说明这个值已经在正确位置了（或者重复了不需要再处理），就不交换，跳出循环

举例说明

以 nums = [3, 4, -1, 1] 为例，n = 4

第一步：交换归位

i	nums（交换前）	nums[i]	操作	nums（交换后）
0	[3,4,-1,1]	3，在1~4，3≠nums[2]=-1	交换nums[0]和nums[2]	[-1,4,3,1]
0	[-1,4,3,1]	-1，不在1~4	不交换	[-1,4,3,1]
1	[-1,4,3,1]	4，在1~4，4≠nums[3]=1	交换nums[1]和nums[3]	[-1,1,3,4]
1	[-1,1,3,4]	1，在1~4，1≠nums[0]=-1	交换nums[1]和nums[0]	[1,-1,3,4]
1	[1,-1,3,4]	-1，不在1~4	不交换	[1,-1,3,4]
2	[1,-1,3,4]	3，在1~4，3==nums[2]=3	已在正确位置，不交换	[1,-1,3,4]
3	[1,-1,3,4]	4，在1~4，4==nums[3]=4	已在正确位置，不交换	[1,-1,3,4]

第二步：查找结果

遍历数组，找到第一个 nums[i] != i+1 的位置：

nums[0] = 1 = 0+1 ✓
nums[1] = -1 ≠ 1+1 = 2 ✗ → 缺失的最小正整数为 2

最终结果为 2

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