LeetCode题目:缺失的第一个正数

题目描述:

给你一个未排序的整数数组,请你找出其中没有出现的最小的正数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
提示:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外间。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

做这道题目的第一件事就是先将数组排列,排列之后的数组,小于0的部分不用管,如果整个数组的数都是小于0的,直接返回1。先找出数组的第一个大于0的数,如果这个数不是1,则1就是缺失的第一个正数了,返回1。如果第一个大于0的数就是1,那么需要找到数组后面的部分是否是连贯的,如果是连贯,则返回最后一个数+1,如果不是连贯的,找到断点处,返回断点处的值+1。

代码(Java):

public class doingmyself {
	public static void main(String[] args) {
		int[] nums = {-1,4,2,1,9,10};
		System.out.println(firstMissingPositive(nums));
	}
	
	public static int firstMissingPositive(int[] nums) {
		Arrays.sort(nums);  //先对数组进行排列
		int len = nums.length;  
		int ans = 0;  //返回值
		int term = 0;  //term用来存排列之后找出的第一个大于0的正数
		int curr = 0;  //term对应在数组中的位置
		boolean flag = true;  //表示是否数组里面大于0的数字从1开始并且连贯,这样却是的第一个正整数就是连贯数字的最后一个+1
		for(int i=0;i<len;i++) { //循环找出第一个正整数
			if(nums[i]>0) {
				term = nums[i];
				curr = i;
				break;  //找到第一个就可以停止循环了
			}
		}
		//这个是数组里面全部都是负数的情况  或者找到的第一个整数不是1
		if(term == 0 || term != 1) { //这种情况,缺失的第一个正整数就是1
			ans = 1;
			return ans;
		}
		//第一个整数是1的情况
		for(int i = curr;i<len-1;i++) {
			if(nums[i+1]-nums[i]>1) { //循环找出数组里面有相邻两个数差大于2的数
				ans = nums[i]+1;
				flag = false;  //标志位变为false,这样就不是数组里面大于零的数连贯的情况
				break; //找到一个就可以停止
			}
		}
		if(flag) {  //返回数组的最后一个数+1
			ans = nums[len-1]+1;
		}
		return ans;
    }
}