本文主要是介绍Leetcode41缺失的第一个正数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：原地哈希表
长度为N的数组，没有出现过的正整数一定是1~N+1中的一个。
此时会思考能不能用一个哈希表来保存出现过的1~N+1的数，然后从 1 开始依次枚举正整数，并判断其是否在哈希表中
但是题目要求常数级别的空间，就不能使用N的哈希表了。
这里将原数组当做哈希表，使用标记的办法来标记出现过的正整数，最后遍历数组，第一个没出现的下标+1就是答案
怎么样进行标记呢？
- 先遍历一遍数组，将非正整数置为N+1
- 再遍历一遍数组，将1~N正整数对应的下标位置置为负数
- 最后遍历一遍数组，第一个不是负数的位置i+1就是没出现过的最小的正整数
class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;for(int i = 0;i<len;i++){if(nums[i]<=0){nums[i] = len+1;}}for(int i = 0;i<len;i++){int num = Math.abs(nums[i]);if(num<=len&&num>0){nums[num-1] = -Math.abs(nums[num-1]);}}for(int i = 0;i<len;i++){if(nums[i]>=0){return i+1;}}return len+1;}
}这篇关于Leetcode41缺失的第一个正数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
