思路:原地哈希表
长度为N的数组,没有出现过的正整数一定是1~N+1中的一个。
此时会思考能不能用一个哈希表来保存出现过的1~N+1的数,然后从 1 开始依次枚举正整数,并判断其是否在哈希表中
但是题目要求常数级别的空间,就不能使用N的哈希表了。
这里将原数组当做哈希表,使用标记的办法来标记出现过的正整数,最后遍历数组,第一个没出现的下标+1就是答案
怎么样进行标记呢?文章来源:https://www.toymoban.com/news/detail-745020.html
- 先遍历一遍数组,将非正整数置为N+1
- 再遍历一遍数组,将1~N正整数对应的下标位置置为负数
- 最后遍历一遍数组,第一个不是负数的位置i+1就是没出现过的最小的正整数
文章来源地址https://www.toymoban.com/news/detail-745020.html
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缺失的第一个正数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!