目录
题目
题目链接
思路
阶段1：重新排列数组
阶段2：寻找第一个缺失的正数
复杂度
时间复杂度：O(n)
空间复杂度：O(1)
代码
题目
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
题目链接
41. 缺失的第一个正数 – 力扣（LeetCode）
https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
思路
核心思想：原地哈希
关键观察：
对于一个长度为 n 的数组，缺失的第一个正数只能在 [1, n+1] 范围内：
1. 如果数组包含了 1 到 n 的所有数字 → 答案是 n+1
2. 否则，答案一定是 1 到 n 之间的某个数
为什么？
假设缺失的第一个正数是 x：
– 如果 x > n，那么数组一定包含了 1 到 n 的所有数字
– 所以 x 最大只能是 n+1
阶段1：重新排列数组
目标：让数字 nums[i] 放到下标为 nums[i]-1 的位置上
例如：数字 3 应该放到下标 2 的位置上
方法：遍历数组，对于每个位置 i：
如果 nums[i] 在 [1, n] 范围内，且不在正确位置上：
交换 nums[i] 和 nums[nums[i]-1]
重复这个过程直到 nums[i] 不在 [1, n] 范围内或已在正确位置
阶段2：寻找第一个缺失的正数
遍历数组，检查每个位置 i：
如果 nums[i] != i+1，说明 i+1 缺失
返回 i+1
如果所有位置都正确，返回 n+1
复杂度
时间复杂度：O(n)
外层循环：执行 n 次
内层 while 循环：每次交换都会将一个数字放到正确位置
一旦一个数字被放到正确位置，它就不会再被移动
所以总操作次数 = O(2n) = O(n)
空间复杂度：O(1)
除了输入的数组 nums，只使用了常数个额外变量
空间复杂度：O(1)
代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size(); // 数组长度
// 第一阶段：将每个数字放到它应该在的位置上
// 思路：如果 nums[i] 是正整数且在 [1, len] 范围内，
// 它应该被放在 nums[nums[i]-1] 的位置上
for (int i = 0; i < len; i++) {
// 条件：当前数字在有效范围内，且不在正确位置上
while (nums[i] >= 1 && nums[i] <= len && nums[nums[i] – 1] != nums[i]) {
// 将当前数字交换到它应该在的位置上
swap(nums[i], nums[nums[i] – 1]);
// 注意：交换后，新的 nums[i] 可能也需要调整，所以用 while 循环
}
}
// 第二阶段：扫描数组，找到第一个不在正确位置上的数字
for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
// 位置 i 上应该是 i+1，如果不是，说明 i+1 缺失
return i + 1;
}
}
// 第三阶段：如果数组包含了 1 到 len 的所有数字
// 那么缺失的第一个正数就是 len+1
return len + 1;
}
};
