缺失的第一个正数：原地哈希与索引映射的极致压榨

适读人群：Java 开发者、冲击大厂算法面试的工程师 | 阅读时长：约22分钟 | 难度：Hard

---

开篇故事

这是 LeetCode 上 Hard 难度里我最喜欢的一道题，没有之一。

不是因为它难，而是因为它的最优解展示了一种近乎"无中生有"的技巧——在 O(1) 空间的约束下，用数组本身作为哈希表。

我第一次刷这道题是2019年底，当时拿到题目，很快想到了 HashSet 的解法，O(n) 时间 O(n) 空间，提交通过了。然后看了一眼要求：O(1) 空间。我当时的第一反应是："这怎么可能？"

硬想了二十分钟，翻了一眼提示，才恍然大悟：下标本身就可以当哈希表用。把数组里的正整数放到它们"应该在"的位置——值 k 放到下标 k-1——然后扫描一遍找第一个"没归位"的位置，就是答案。

这个技巧叫"原地哈希"（In-place Hashing）或者"索引映射"。它充分利用了"答案一定在 [1, n+1] 范围内"这个约束，把本来需要额外空间的哈希结构，免费嵌入到了原数组里。

---

一、题目解析

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

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

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

输入输出示例：

示例 1：

输入：nums = [1,2,0]
输出：3
解释：[1,2] 都在，最小缺失正整数是 3

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：[1,3,4] 在，[2] 缺失

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小正整数 1 不存在

边界情况 4（连续正整数）：

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

边界情况 5（只有负数和零）：

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

关键约束分析：

• 答案范围是 [1, n+1]（n 个元素，最多能覆盖 1 到 n，所以答案最大是 n+1）
• 这个约束是原地哈希可行的根本原因

---

二、解法一：HashSet（O(n) 空间，不满足约束）

思路：把所有正整数存入 HashSet，从 1 开始逐一检查是否在集合中。

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        
        for (int i = 1; i <= nums.length + 1; i++) {
            if (!set.contains(i)) return i;
        }
        return nums.length + 1;
    }
}

时间复杂度：O(n)，空间复杂度：O(n)。不满足 O(1) 空间要求。

---

三、解法二：排序（O(n log n) 时间，不满足约束）

先排序，再线性扫描找第一个缺失的正整数。

class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int expected = 1;
        for (int num : nums) {
            if (num == expected) expected++;
        }
        return expected;
    }
}

时间复杂度：O(n log n)。不满足 O(n) 时间要求。

---

四、解法三：原地哈希（工业级最优解，O(n) 时间 O(1) 空间）

核心洞见

答案在 [1, n+1] 范围内，所以只关心数组中 1 到 n 的正整数是否存在。

把值为 k（满足 1 <= k <= n）的元素放到下标 k-1 的位置。这样 nums[k-1] == k 表示 k 存在。

如何原地实现？ 遍历数组，每次把 nums[i] 放到它"应该在"的位置（如果这个位置还没放好的话）：

• 如果 nums[i] 在 [1, n] 范围内，且 nums[nums[i]-1] != nums[i]（目标位置上不是正确的值），就交换 nums[i] 和 nums[nums[i]-1]
• 重复交换，直到当前位置的值不能被放到有效目标位置

关键： 为什么交换后不 i++？因为交换来的新值 nums[i] 也需要被放到它的目标位置，需要继续处理当前 i 的位置直到它的值不满足交换条件。

算法流程

完整 Java 代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // 第一步：原地哈希——把每个在 [1, n] 范围内的值放到对应位置
        for (int i = 0; i < n; i++) {
            // while 循环：当 nums[i] 应该放到其他位置，且那个位置还没有正确的值时，交换
            while (nums[i] >= 1 && nums[i] <= n    // nums[i] 是有效正整数（在范围内）
                   && nums[nums[i] - 1] != nums[i]) { // 目标位置的值不等于 nums[i]（未归位）
                // 交换：把 nums[i] 放到它应该在的位置 nums[i]-1
                int targetIdx = nums[i] - 1;
                int temp = nums[targetIdx];
                nums[targetIdx] = nums[i];
                nums[i] = temp;
            }
        }
        
        // 第二步：扫描——找第一个"没归位"的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;  // 下标 i 对应的正整数 i+1 缺失
            }
        }
        
        // 所有 1 到 n 都存在，答案是 n+1
        return n + 1;
    }
}

复杂度分析

时间复杂度：O(n)

看起来有嵌套 while 循环，但实际上每个元素最多被交换一次（每次交换都把一个元素放到了它的最终位置，不会再被交换走）。总交换次数 <= n 次，加上两次线性扫描，总体 O(n)。

空间复杂度：O(1)

原地操作，只用了临时变量 temp 和 targetIdx。

我在 LeetCode 提交，运行时间 0ms，击败 100% 的 Java 用户。

---

五、举一反三

同类型题目（原地哈希/索引映射）

LeetCode 442. 数组中重复的数据

数组中所有元素在 [1, n] 范围内，找所有出现两次的元素。利用下标映射：遍历时，把 nums[|nums[i]|-1] 取反，如果取反时发现已经是负数，说明 |nums[i]| 已经被访问过两次（重复）。

LeetCode 448. 找到所有数组中消失的数字

和 LeetCode 41 类似，找 [1, n] 中所有缺失的数字（不只是最小的那个）。同样用取反标记法或原地哈希。

LeetCode 268. 丢失的数字

[0, n] 中缺失的一个数字。数学方法：期望总和 - 实际总和，O(n) O(1)，更简单。

LeetCode 287. 寻找重复数

上一篇讲过，用 Floyd 判圈。

原地哈希通用模板

// 适用于 "数组元素在 [1, n] 范围内" 的问题
for (int i = 0; i < n; i++) {
    while (/* nums[i] 需要放到其他位置 */ && /* 目标位置不正确 */) {
        swap(nums, i, nums[i] - 1);  // 交换到目标位置
    }
}
// 后续扫描找答案

面试中的变体和追问

1. 为什么 while 循环里要检查 nums[nums[i]-1] != nums[i]？ 答：如果目标位置已经有正确的值，就不要再交换了（避免无限循环）。例如数组里有两个 1，nums[i]=1, nums[0]=1，不检查的话会一直把 1 和 1 交换，死循环。

2. 能否用标记（取反）而不是移位？ 答：可以，另一种方案是把"值 k 存在"标记为 nums[k-1] = -|nums[k-1]|（取负），最后扫描找第一个正数位置。但需要处理 0（取反后还是 0），以及区分"原本就是负数"的情况，代码稍复杂。原地交换更直观。

---

六、踩坑实录

坑一：while 循环条件忘记检查目标位置的值

现象： 数组中有两个相同的值（如 [1,1]），程序无限循环。

原因： while 循环条件只检查了 nums[i] 是否在有效范围内，忘记了检查 nums[nums[i]-1] != nums[i]。当 nums[i] = 1, nums[0] = 1 时，两者相等，交换之后 nums[i] 还是 1，无限循环。

解法： 必须加上 nums[nums[i]-1] != nums[i] 这个条件：只有当目标位置的值不等于 nums[i] 时才交换，否则直接 break 出 while 循环。

坑二：交换时用了直接赋值没有中间变量

现象： 交换后 nums[i] 的值不对，原地数据被覆盖丢失。

原因：

// 错误：直接赋值，丢失了 nums[targetIdx] 的原始值
nums[targetIdx] = nums[i];
nums[i] = nums[targetIdx]; // 此时 nums[targetIdx] 已经是 nums[i] 了

解法： 使用临时变量：

int temp = nums[targetIdx];
nums[targetIdx] = nums[i];
nums[i] = temp;

或者使用 XOR 交换（不需要临时变量，但可读性差）：nums[i] ^= nums[targetIdx]; nums[targetIdx] ^= nums[i]; nums[i] ^= nums[targetIdx];（注意 i != targetIdx 时才能用 XOR）。

坑三：第二步扫描返回值差一

现象： 某些输入下，返回的答案比预期小一。

原因： 第二步扫描时，nums[i] 应该等于 i+1（下标 0 对应正整数 1，下标 1 对应正整数 2，...），如果不等，说明 i+1 这个正整数缺失。容易写成 return i 而不是 return i+1，差了 1。

解法： 扫描时严格按 nums[i] != i+1 判断，返回 i+1。

---

七、总结

LeetCode 41 是"用好约束条件"的最佳示范。答案在 [1, n+1] 这个约束，使得我们可以把数组下标当成隐式的哈希桶，完全不需要额外空间。

三条核心要点：

1. 答案在 [1, n+1] 范围内，所以只需要关心 1 到 n 是否都存在。这个约束是一切的基础。

2. 原地哈希的操作：把值 k 放到下标 k-1，用 while 循环持续交换直到当前位置不满足交换条件（目标位置已经有正确的值，或者 nums[i] 不在有效范围内）。

3. while 循环的终止条件必须同时检查值的范围和目标位置是否已经归位，缺少任何一个都会导致死循环或者结果错误。

延伸思考：

原地哈希的思想——用数组下标作为哈希桶——是一个重要的编程技巧，适用于"元素值范围等于数组大小"的场景。在内存极度受限的嵌入式系统或者大数据处理（无法加载完整的哈希表）中，这个技巧非常有用。理解了这道题，LeetCode 448（找消失的数字）、442（找重复的数字）都可以用类似的方式解决。

---

本系列第 501-520 期至此全部完结。

这二十道题覆盖了数组与字符串的核心算法模式：

• 哈希表加速查找（501、509）
• 双指针与滑动窗口（502、503、504、505）
• 单调栈（505、506）
• 字符串算法（507、508）
• 前缀和（509、510、512）
• 动态规划（511、513、514、519）
• 矩阵操作（515、516）
• 特殊算法（517 Floyd、518 Boyer-Moore）
• 原地哈希（520）

每一种模式都值得反复练习，直到遇到题目能自然地识别出该用哪种武器。