leetcode:41. 缺失的第一个正数

向右看齐 2022-04-13 06:40 151阅读 0赞

## 题目: ##

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

输入: \[1,2,0\]  
输出: 3  
示例 2:

输入: \[3,4,-1,1\]  
输出: 2  
示例 3:

输入: \[7,8,9,11,12\]  
输出: 1  
说明:

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

## 分析: ##

难点在于O(n)的时间复杂度,所以不能排序,分析后不难得出该最小正整数不可能大于数组的长度,  
定义自然排列为类似  
\[1,2,3,4,5,6,7\]这样的数组,从头开始遍历数组把每一个能放到数组内自然排列下位置的都交换过去放在自然排列位上,然后从头开始遍历数组,第一个不满足自然排列的即为所需的最小正整数,交换时注意判断两者相等的情况,否则会死循环…

## 代码: ##

public int firstMissingPositive(int[] nums) {
            //从头开始遍历
        	int l = nums.length;
        	
        	for(int i = 0;i<l;i++){
        		while(nums[i]!=i+1&&nums[i]>0&&nums[i]<l+1&&nums[i]!=nums[nums[i]-1]){
        			swap(nums,i,nums[i]-1);
        		}
        	}
        	
        	for(int i = 0;i<l;i++){
        		if(nums[i]!=i+1)
        			return i+1;
        	}
        	
    		return l;
        	
        }
    
    	private void swap(int[] nums, int i, int j) {
    		int temp = nums[i];
    		nums[i]=nums[j];
    		nums[j]=temp;
    	}

## 效率: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]

## 总结: ##

算法时间复杂度没有足够低到O(n)级别,有待日后优化…  
TODO:)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220413/ab7dbfd300e1477f97b06489f02e6ddf.png