题目大意：
缺失的第一个正数
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3
示例 2:
输入: [3,4,-1,1] 输出: 2
示例 3:
输入: [7,8,9,11,12] 输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=41
解题思路分析：
缺失的第一个正数，就是缺少的最小的那个正数，我们应该先明确这个正数的取值范围，最小值应该是1，也就是说如果数组中不存在1的话，那么返回值应该是1。那么最大值的可能是多少呢？假设数组中存在n个数字，最极端的情况是这n个数字分别是1到n，因此，此时缺失的最小正数应该是n+1，除此以外，不论1到n之间缺少哪个数字，该数字一定是小于n+1的。这样，我们就将返回结果的范围缩小到了数字区间[1, n](n为数组长度)之间。
我们定义一个boolean型数组has[]，数组长度为n+1，循环一遍数组，记录数字1到n之间哪些数字出现过，然后再循环has，当has[i]为false时，表示数字i没有出现过，可返回i。如果has数组中的数字全都出现过，那么返回n+1。
实现代码：
public int firstMissingPositive(int[] nums) {
// 记录出现过的数字
boolean[] has = new boolean[nums.length+1];
for(int n : nums){
if(n<=0 || n>=has.length) continue;
has[n]=true;
}
// 找到最小的没有出现过的数字
for(int i=1;i<has.length;i++){
if(!has[i]) return i;
}
// 1到n全出现过时，返回n加1，即has数组长度
return has.length;
} 本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for First Missing Positive.
Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for First Missing Positive.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-41-first-missing-positive-解题思路分析/