第一个缺失的正数
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
分析
由于线性时间和常数空间的要求,我们开不了数组,用不了哈希表,不能排序。
能用的就只有数组本身以及额外常数个变量。。。
我们考虑如果整数都出现,那么最后数组排列应该是[1,2,3,4,5,…,n],每个都是递增1。
于是乎,如果我们最后也排列成这种形式,那么只要不满足nums[i]-nums[i-1]不等于1,那么就找到了最小的未出现的整数,但是我们没法排序。
所以我们可以强行另数组下标和存的值产生联系-> 令数字i出现在下标为i-1的位置,如果会越界则不做处理。
比如[3,4,-1,1]->[-1,4,3,1]->[-1,1,3,4]->[1,-1,3,4];
代码
class Solution {
public int firstMissingPositive(int[] nums) {
for(int i=0;i<nums.length;){
if(nums[i]>0&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){
//确定nums[i]的值对应的下标不越界,同时排除num[i]本身位置正确或者nums[i]应该放入的位置nums[i]-1原本就是nums[i](如[1,1])
int index = nums[i];//
nums[i] = nums[index -1];
nums[index -1]=index;
//换位置之后需要继续判断换过来的值是否在对的位置上,因此不能i++;
}else{
i++;
}
}
for(int i=0;i<nums.length;i++){
if(nums[i]!=i+1){
return i+1;
}
}
return nums.length+1;
}
}
今天的文章缺失的第一个正数java_leetcode最大数[通俗易懂]分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/87199.html