给你一个未排序的整数数组 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 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n;i++){
while(nums[i]>0&&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;
}
return n+1;
}
};第一次遍历（重新排序）
我们需要把所有在 [1, n] 范围内的正整数 x放到索引 x−1的位置上。我们利用一个 while 循环来完成这个任务。
条件判断:
nums[i] > 0: 只考虑正整数。nums[i] <= n: 只考虑不大于数组长度n的整数。nums[nums[i] - 1] != nums[i]: 确保nums[i]应该放在nums[nums[i] - 1]位置上，并且这个位置上还没有正确的值。
交换: 将
nums[i]放到它正确的位置上，即nums[nums[i] - 1]。每次交换后，我们还需要重新检查当前位置的值是否已经在正确的位置上，所以需要用while循环。
例如，对于数组 [3, 4, -1, 1]：
- 初始数组：
[3, 4, -1, 1] - 第一次交换：
[ -1, 4, 3, 1]（将 3 放到索引 2） - 第二次交换：
[-1, 1, 3, 4]（将 4 放到索引 3） - 第三次交换：
[1, -1, 3, 4]（将 1 放到索引 0）
第二次遍历（查找缺失的正整数）
经过第一次遍历后，数组应该是部分有序的，即 nums[i] 应该等于 i+1。
- 条件判断:
- 遍历数组，如果
nums[i] != i + 1，说明i + 1是缺失的最小正整数。
- 遍历数组，如果
例如，对于上述的有序数组 [1, -1, 3, 4]：
- 遍历到
i = 1时，nums[1]应该是2，但实际上是-1，所以2是缺失的最小正整数。
返回结果
- 如果所有位置上的元素都是正确的，说明数组包含
[1, n]的所有整数，则缺失的最小正整数是n + 1。
总结
这个算法的时间复杂度是 O(n)，因为每个元素最多交换一次。而且使用的是原地交换，所以额外空间复杂度是 O(1)。通过这个过程，我们可以有效地找到缺失的最小正整数。
