原题
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3
示例 2:
输入: [3,4,-1,1] 输出: 2
示例 3:
输入: [7,8,9,11,12] 输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
解法
该题解同步发于leetcode：Java：比官方题解少一次循环
思想
见代码部分
代码
首先这道题有一个隐含条件：如果数组的大小为n，则缺失的第一个正数一定小于或等于n+1（取值最大的情况是数组中的数从1开始连续）
如果不限制常数级别的额外空间，可以使用bitmap的思想去做，如下：
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
//下标对应出现的数-1
int[] exist = new int[n+1];
for(int i:nums){
if(i<=0 || i > n) continue;
exist[i-1] = 1;
}
for(int i = 0;i<n+1;i++){
if(exist[i]==0) return i+1;
}
return 0;
}
}
但是限制了常数级别的额外空间，可以思考一种替换bitmap的原地解法：
既然要原地，肯定需要在原数组上判断当前下标代表的正数是否出现，但又不能修改它的值，因为遍历的时候会用到，可以想到通过修改它的符号来判断。相较于新建一个数组作为bitmap去重的区别是，存在不存在不通过1或0标识，而是通过正负号标识（负号标识出现过，正号标识没出现）
但是数组中存在一些数原来就是负号的，可以先遍历一次让它们都变成正数，0也要变成一个正数，否则无法通过改变符号识别该下标代表的元素是否出现。但变成哪个正数值得考量，否则再次遍历有可能把他们当作数组中原有的数处理，那么就可以把它们设为n+1，因为n+1大于数组的长度，不会映射到数组中的位，可以不进行处理：
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
//先将原来的负数的数置为 `n+1`
for(int i = 0; i < nums.length ; i++){
if(nums[i]<=0 ) {
nums[i] = n+1;
}
}
for(int i = 0; i < nums.length ; i++){
int num = Math.abs(nums[i]);
//绝对值大于数组长度的不处理
if(num<=n && nums[num-1]>0)
nums[num-1] = -nums[num-1];
}
for(int i = 0;i<n;i++){
if(nums[i]>0) return i+1;
}
return n+1;
}
}
成功将官方题解的O(4N)优化成O(3N)~~~
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode41-%e7%bc%ba%e5%a4%b1%e7%9a%84%e7%ac%ac%e4%b8%80%e4%b8%aa%e6%ad%a3%e6%95%b0/
