题目描述：给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
eg:
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1思路描述：题意还是很好理解的，不考虑题目要求的话，就用set去一下重并且对数组排一下序，然后遍历一遍就好了。也可以用hash表去存储一下每个数字然后遍历看下就好。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
set<int> st(nums.begin(), nums.end());
nums.assign(st.begin(), st.end());
int n = nums.size();
for(int i = 0; i < n; i ++){
if(nums[i] > 0){
for(int j = i; j < n; j ++){
if(nums[j] != j - i + 1) return j - i + 1;
}
return nums[n - 1] + 1;
break;
}
}
return 1;
}
};因为题目要求时间复杂度 O(n)，额外空间 O(1)，我们考虑一下，如果相邻整数都在，我们是不是可以把对应整数放在他对应的位置，比如 1 2 3 4 5 应该放在 0 1 2 3 4，这个思路我们之前做题的时候其实也遇到过，和这道题类似，我们把每一个可以放置的整数都放置在它对应的位置，那么再次遍历一遍发现不在对应位置的就可以返回了。
但是负数怎么办呢？
我们看一下这个例子：2 -1 3 1 5
首先 2 应该和 -1 互换 -1 2 3 1 5，现在 nums[0] 变成 -1 了，继续遍历
然后 2 3都在对应位置了，不用换
1 和 -1 换 1 2 3 -1 5，
-1、5不用换
所以只要碰到负数就不用动，因为相应位置如果有数字的话肯定会过来交换的，没有数字的话就遍历到的时候返回就好了。
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[nums[i] - 1], nums[i]);
}
}
for (int i = 0; i < n; i ++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};但是这个思路第一次做的话很难想到，下面也是一个很巧妙的做法。就是把每个数字对应的位置都变成负数，然后遍历一遍，正数对应位置就是缺失的位置。这个应该更容易理解一些。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
bool flag = true;
//先查找数组中是否有 1，没有的话就直接返回 1
for(int i = 0; i < n; i ++){
if(nums[i] == 1) flag = false;
}
if(flag) return 1;
//因为已经有 1 了，不合法数值就赋值 1 就好了，不影响后面计算
for(int i = 0; i < n; i ++){
if(nums[i] <= 0 || nums[i] > n){
nums[i] = 1;
}
}
for(int i = 0; i < n; i ++){
//把每个数字对应位置都变成负数
int pos = nums[i] > 0 ? nums[i] : (-nums[i]);
nums[pos-1] = nums[pos-1] > 0 ? (-nums[pos-1]) : nums[pos-1];
}
for(int i = 0; i < n; i ++){
if(nums[i] > 0) return i + 1;
}
return n + 1;
}
};