老规矩,先上链接(ps,仔细端详了东哥模板的才知道那个分享链接的形式 ,不过好像只能分享语雀里的,所以就直接贴链接了,还是自己的博客写起来顺手2333 )
思路
“你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间。”
感觉这不像是限制反而是提示?感觉就是开个记录数组能解决的事,无视负数即可。大致思路是开个数组记录对应数是否出现过,最后对这个记录数组跑下遍历就能出来。
(其实有想过用多指针,记录正数最值的方法,要是能开个数组可能更容易解)
题解代码
带测试可运行代码
package com.leaf;
public class LosedFirstNum {
public static void main(String[] args) {
int a [] = {3,4,-1,1};
System.out.println(firstMissingPositive(a));
}
public static int firstMissingPositive(int[] nums) {
int len=0;
for (int i = 0; i < nums.length; i++) { if(nums[i]>=len) {
len = nums[i];
}
}
if(len>nums.length) {
len = nums.length;
}
if(len>=1) {
int a [] = new int[len+1];
for(int i=0;i<nums.length;i++) { if(nums[i]>=0&&nums[i]<len+1) {
a[nums[i]] = 1;
}
}
int j=1;
while(a[j]!=0) {
j++;
if(j==a.length) {
break;
}
}
return j;
}else {
return 1;
}
}
}
心得
- 其实还是有坑的,注意记录数组的大小,因为整数肯定是间断的,所以出现的整数如果大于数组的长度,那么记录数组最大就开到数组的长度就行。
- 注意全负与数组长度为1的情况。