当前位置：首页 > news >正文

【LeetCode Hot 100】 - 缺失的第一个正数完全题解

news 2026/7/18 18:28:37

题目描述

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

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

示例 1：

text

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

示例 2：

text

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

示例 3：

text

输入：nums = [7,8,9,11,12] 输出：1 解释：1 不在数组中

示例 4：

text

输入：nums = [1] 输出：2

示例 5：

text

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

解题思路

核心思想：对于一个长度为n的数组，缺失的第一个正数一定在[1, n+1]范围内。

证明：

如果数组包含了1到n的所有正整数，那么答案就是n+1
否则，答案就是[1, n]中缺失的那个数

因此，我们只需要关注1到n范围内的数字，将它们放到正确的位置上。

方法一：哈希表（不满足空间要求）

思路

将所有数字存入哈希表，然后从 1 开始递增查找。

代码实现

java

public int firstMissingPositive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } int missing = 1; while (set.contains(missing)) { missing++; } return missing; }

复杂度分析

时间复杂度：O(n) — 一次遍历 + 最多 n 次查找
空间复杂度：O(n) — 哈希表存储所有元素

优缺点

✅ 思路简单直观
❌ 空间复杂度 O(n)，不满足题目常数空间要求

方法二：排序（不满足时间要求）

思路

排序后跳过负数和零，然后找第一个缺失的正数。

代码实现

java

public int firstMissingPositive(int[] nums) { Arrays.sort(nums); int missing = 1; for (int num : nums) { if (num == missing) { missing++; } else if (num > missing) { break; } } return missing; }

复杂度分析

时间复杂度：O(n log n) — 排序
空间复杂度：O(log n) — 排序所需空间（或 O(1) 如果原地排序）

优缺点

✅ 代码简单
❌ 时间复杂度 O(n log n)，不满足题目 O(n) 要求

方法三：原地哈希（最优解）⭐

核心思想

利用数组索引作为哈希表，将数字x放到索引x-1的位置上。

规则：

只处理1到n范围内的数字
将nums[i]放到nums[nums[i] - 1]的位置
最终，如果nums[i] != i + 1，则i+1就是缺失的第一个正数

算法步骤

遍历数组，对于每个元素nums[i]：
- 如果1 <= nums[i] <= n且nums[i]不在正确位置上，就交换
- 交换后继续检查新换过来的数字
再次遍历，找到第一个nums[i] != i + 1的位置
如果都正确，返回n + 1

代码实现

java

public int firstMissingPositive(int[] nums) { int n = nums.length; // 第一步：将数字放到正确的位置 for (int i = 0; i < n; i++) { // 循环交换，直到 nums[i] 不在 [1, n] 范围内或者已经在正确位置 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { swap(nums, i, nums[i] - 1); } } // 第二步：找到第一个位置不对的数字 for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; } } // 第三步：如果都在正确位置，返回 n+1 return n + 1; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

手动模拟

以nums = [3, 4, -1, 1]为例（n=4）：

第一步：原地交换

i	nums 数组	操作
0	[3,4,-1,1]	nums[0]=3，范围1-4，目标位置2，交换 nums[0] 和 nums[2] → [ -1,4,3,1 ]
0	[-1,4,3,1]	nums[0]=-1，不在范围，跳过
1	[-1,4,3,1]	nums[1]=4，目标位置3，交换 nums[1] 和 nums[3] → [ -1,1,3,4 ]
1	[-1,1,3,4]	nums[1]=1，目标位置0，交换 nums[1] 和 nums[0] → [ 1,-1,3,4 ]
1	[1,-1,3,4]	nums[1]=-1，不在范围，跳过
2	[1,-1,3,4]	nums[2]=3，目标位置2，已经在正确位置
3	[1,-1,3,4]	nums[3]=4，目标位置3，已经在正确位置

最终数组：[1, -1, 3, 4]

第二步：查找缺失正数

索引 i	期望值 i+1	实际值 nums[i]	是否匹配
0	1	1	✅
1	2	-1	❌ 返回 2

结果：2✅

另一种写法（标记法）

思路

先将所有负数和零改为n+1（占位符）
遍历数组，将|nums[i]|对应位置的数字标记为负数
遍历数组，第一个正数的位置就是答案

代码实现

java

public int firstMissingPositive(int[] nums) { int n = nums.length; // 第一步：将所有负数、0 改为 n+1（这些数字不影响结果） for (int i = 0; i < n; i++) { if (nums[i] <= 0) { nums[i] = n + 1; } } // 第二步：使用索引作为哈希表，标记出现过的正数 for (int i = 0; i < n; i++) { int num = Math.abs(nums[i]); if (num <= n) { // 将 num-1 位置的数字标记为负数 if (nums[num - 1] > 0) { nums[num - 1] = -nums[num - 1]; } } } // 第三步：找到第一个正数的位置 for (int i = 0; i < n; i++) { if (nums[i] > 0) { return i + 1; } } // 如果全部被标记，返回 n+1 return n + 1; }

手动模拟（标记法）

nums = [3, 4, -1, 1]（n=4）

第一步：处理负数和零

text

[3, 4, -1, 1] → [-1 ≤ 0? 改为5] → [3, 4, 5, 1]

第二步：标记出现过的数字

num=3，标记位置2：[3, 4, 5, 1]→[3, 4, -5, 1]
num=4，标记位置3：[3, 4, -5, 1]→[3, 4, -5, -1]
num=5，跳过（5 > 4）
num=1，标记位置0：[3, 4, -5, -1]→[-3, 4, -5, -1]

第三步：找第一个正数

i=0，nums[0] = -3 < 0
i=1，nums[1] = 4 > 0 → 返回 i+1 = 2 ✅

复杂度分析（两种写法）

时间复杂度：O(n) — 最多三次线性扫描
空间复杂度：O(1) — 原地修改数组

优缺点

✅ 时间复杂度 O(n)
✅ 空间复杂度 O(1)
✅ 满足题目要求
⭐ 面试推荐写法

方法四：置换法（带边界优化）

思路

与方法三相同，但增加了条件判断，避免无效交换。

代码实现

java

public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { // 只有当 nums[i] 在 [1, n] 范围内，且不在正确位置时才交换 while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) { int targetIndex = nums[i] - 1; // 交换 int temp = nums[i]; nums[i] = nums[targetIndex]; nums[targetIndex] = temp; } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; } } return n + 1; }

方法对比总结

方法	时间复杂度	空间复杂度	是否满足题目要求	推荐度
哈希表	O(n)	O(n)	❌ 空间不满足	⭐⭐
排序	O(n log n)	O(log n)	❌ 时间不满足	⭐⭐
原地哈希（交换法）	O(n)	O(1)	✅ 完美满足	⭐⭐⭐⭐⭐
原地哈希（标记法）	O(n)	O(1)	✅ 完美满足	⭐⭐⭐⭐

图文详解（以交换法为例）

核心思想图解

text

目标：将数字放到正确的位置 数字 x 应该放在索引 x-1 的位置 数组索引: 0 1 2 3 4 5 正确数字: 1 2 3 4 5 6

交换过程可视化

text

初始数组: [3, 4, -1, 1] (n=4) 步骤1: i=0, nums[0]=3 3 应该去索引 2 交换 nums[0] 和 nums[2] [ -1, 4, 3, 1 ] 步骤2: i=0, nums[0]=-1 (不在1-4范围，跳过) i=1, nums[1]=4 4 应该去索引 3 交换 nums[1] 和 nums[3] [ -1, 1, 3, 4 ] 步骤3: i=1, nums[1]=1 1 应该去索引 0 交换 nums[1] 和 nums[0] [ 1, -1, 3, 4 ] 步骤4: i=1, nums[1]=-1 (跳过) i=2, nums[2]=3 (已在正确位置) i=3, nums[3]=4 (已在正确位置) 最终数组: [1, -1, 3, 4] 检查: 索引0: 期望1 → 实际1 ✅ 索引1: 期望2 → 实际-1 ❌ 返回2

为什么时间复杂度是 O(n)？

虽然使用了while循环，但每个数字最多被交换一次，一旦放到正确位置就不会再移动。总交换次数 ≤ n，因此整体是 O(n)。

常见问题 Q&A

Q1：为什么要限制范围在 1 到 n？

A：因为答案只可能在这个范围内。如果[1, n]都出现了，答案就是n+1。超过n的数字我们可以忽略。

Q2：交换法中的 while 循环会不会导致死循环？

A：不会。每次交换都会把一个数字放到正确位置，正确位置的数字不会再被移动。最多交换 n 次后循环结束。

Q3：标记法中为什么要用绝对值？

A：因为标记过程中可能把某个位置变成了负数，取绝对值可以获取原始数值。

Q4：两种原地哈希方法哪个更好？

A：

交换法：更直观，更容易理解，推荐面试使用
标记法：需要两次遍历，代码稍复杂，但思想也很巧妙

Q5：如何处理数组中已有的重复数字？

A：交换时会自动处理。当遇到重复时，nums[nums[i] - 1] != nums[i]条件为 false，不会交换，避免了死循环。

边界情况处理

输入	输出	说明
`[]`	1	空数组，第一个正数是1
`[0]`	1	只有0，1缺失
`[-1, -2, -3]`	1	全是负数，1缺失
`[1]`	2	有1，缺失2
`[1, 2, 3, 4, 5]`	6	1-5都在，返回6
`[1, 1, 1, 1]`	2	重复数字，缺失2