本文主要是介绍leetcode 41.缺失的第一个正数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：首先就是O(n)时间复杂度，O(n)空间复杂度的，其实很简单，我们只需要定义一个哈希表，遍历一遍数组的时候计数数组中的元素就行；之后再次遍历一遍，只不过这回是从1开始比照哈希表里存不存在这个正整数，从而获得答案。
class Solution {public int firstMissingPositive(int[] nums) {Map<Integer,Integer>map=new HashMap<Integer,Integer>();for(int i=0;i<nums.length;i++){map.put(nums[i],map.getOrDefault(nums[i],0)+1);}int res=0;for(int i=1;;i++){if(!map.containsKey(i)){res=i;break; }}return res;}
}但是，这不是题目本身的初衷。那么我们怎么想到用O（1）的空间复杂度来实现呢？这里我们需要明确一点，那就是我们需要找的正整数一定会在[1,N+1]的范围之内。为什么呢？
我们可以这样想：如果[1,N]的数全在这个数组当中，那么最小的正整数就应该是N+1；
那么如果这个数组中的数全都不是在[1,N]内的数，那么我们就会看到最小正整数就应该是1.那么这个区间就自然而然地推理出来在这个范围之内了。
并没有严格的证明，只是考虑了两种极端的情况，来判断最小正整数的最大值和最小值。
既然答案就在这个区间内，我们怎么判断它是哪一个呢？题解中给出的方法就是如果遍历到数x，那么我们就在坐标x-1的位置标记。如此标记全部完毕之后，如果全部标记完了，那么就说[1,N]的数全在这个数组中；
那么如果没有标记完呢？标记要怎么标记呢？标记就可以让正数变成负数。如果一个数本身就是负数，我们就把这个负数变成>=N+1的数，这样就不影响我们标记数组位置了。这个时候，当我们标记完之后出现正数的坐标+1就是答案了。
class Solution {public int firstMissingPositive(int[] nums) {for(int i=0;i<nums.length;i++){if(nums[i]<=0){nums[i]=nums.length+2;}}for(int i=0;i<nums.length;i++){if(Math.abs(nums[i])>0&&Math.abs(nums[i])<=nums.length){if(nums[Math.abs(nums[i])-1]>0)nums[Math.abs(nums[i])-1]=-nums[Math.abs(nums[i])-1];elsecontinue;}}boolean flag=false;int res=0;for(int i=0;i<nums.length;i++){if(nums[i]>0){flag=true;res=i+1;break;}}return flag==true?res:nums.length+1;}
}这篇关于leetcode 41.缺失的第一个正数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
