给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案
这道题是哈希思想+原地哈希的经典面试题，要求O（n）时间+O（1）空间，核心思路是把数组本身当作哈希表，让每个数字num放到下标num-1的位置。
核心原理：
1.缺失的最小正整数，一定在[1,n+1]范围内
- 例：[1，2，3]->缺失4
- 例：[3，4，-1，1] -> 缺失2
2.遍历数组，把每个正数x放到下标x-1的位置
3.再次遍历，第一个下标i不满足nums[i] = i+1 , i+1就是答案
代码逐行解释：
第一步：原地调整数字位置
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i])
swap(nums[i], nums[nums[i]-1]);
- 只处理1~n之间的正数（超出范围的数不用管）
- 把数字x交换到下标x-1
- 循环交换，直到当前位置数字正确/超出范围
示例：[3,4,-1,1]
调整后 → [1, -1, 3, 4]
第二步：查找缺失数字
遍历数组，第一个数字！=下标+1的位置，就是答案：
- [1, -1, 3, 4]
- 下标 0：1=0+1 ✔️
- 下标 1：-1≠1+1 ❌ → 返回 2
特殊情况
数组是 [1,2,3] → 全部匹配 → 返回 4（n+1）
复杂度
时间复杂度：O (n)（每个数字最多交换一次）
空间复杂度：O (1)（仅用临时变量，无额外数组）
总结：
核心：用数组本身做哈希，让nums[i]=i+1
两步走：调整数字位置->遍历找答案
完美满足：O (n) 时间 + O (1) 空间，面试高频最优解
注意：
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i])
swap(nums[i], nums[nums[i]-1]);这里的while绝对不能换成if，必须用while
解释：
因为一次交换可能不够！，交换后，新换到i位置的数字，可能仍然需要再次交换
if朱慧判断/交换1次
while会一直交换，直到这个位置数字正确为止
举个例子（彻底懂）
数组：[3, 4, -1, 1]
n = 4
我们看 **i = 0 **这个位置：
nums[0] = 3
用 while（正确）
- 3 应该放到下标 2
交换 → nums = [-1, 4, 3, 1] - 现在 nums[0] = -1
不在 1~4 范围内 →** 停止**
✅ 位置 0 处理完毕
用 if（错误）
- 3 应该放到下标 2
交换 → nums = [-1, 4, 3, 1] - if 执行完直接退出，不再检查新数字
- 循环继续到 i=1
nums[1] = 4 → 换到下标 3
交换 → [-1,1,3,4] - 现在 nums[1] = 1，if 又只交换一次
1 应该放到下标 0！
但 if 不会再处理了！
最终数组变成：
[-1, 1, 3, 4]
❌ 数字 1 永远放不到正确位置！答案错误！
一句话总结
if = 只交换 1 次
while = 交换到正确为止
我们需要的是：
把当前位置处理到完全正确，再去下一个位置
所以必须用while！
完整代码实现如下：
#include
#include
using namespace std;
int firstMissingPositive(vector
int n = nums.size();// 第一步：原地哈希，把每个正数放到正确位置
for (int i = 0; i < n; ++i) {// 只有当数字在 [1,n] 范围内，且不在正确位置时，才交换while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {swap(nums[i], nums[nums[i] - 1]);}
}// 第二步：遍历找第一个不匹配的位置
for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) {return i + 1;}
}// 数组是 [1,2,...,n]，返回 n+1
return n + 1;
}
// 测试主函数
int main() {
vector<int> nums1 = {3, 4, -1, 1};
cout << firstMissingPositive(nums1) << endl; // 输出 2vector<int> nums2 = {1, 2, 0};
cout << firstMissingPositive(nums2) << endl; // 输出 3vector<int> nums3 = {7, 8, 9, 11};
cout << firstMissingPositive(nums3) << endl; // 输出 1
return 0;
}