[算法]缺失的第一个正数——LeetCode.41

老规矩，先上链接（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. 其实还是有坑的，注意记录数组的大小，因为整数肯定是间断的，所以出现的整数如果大于数组的长度，那么记录数组最大就开到数组的长度就行。
2. 注意全负与数组长度为1的情况。