题目:
Given an unsorted integer array, find the first missing positive integer.
For example,Given[1,2,0]return3,and[3,4,-1,1]return2.
Your algorithm should run inO(n) time and uses constant space.
题意:
给定一个未排序的整数数组,,找出第一个错过的正整数。
比如:
给定[1,2,0]返回3,
) 时间复杂度和常数空间。
算法分析:
) 的时间复杂度,所以快速排序显然是行不通的。
因此为了搜寻元素,这里采用数组的下标作为其索引,即对数组的元素进行交换,将正数i放到i-1的位置上,对于负数和大于数组长度的元素弃之不顾。这样线性扫描一下数组就能得到第一个不存在的正数,即第j位置的元素不等于j+1。
AC代码:
public class Solution {public int firstMissingPositive(int[] A){//将正数放到值-1的位置上,这样1放在0号位置,2放在1号位置,。。。。if(A==null || A.length==0)return 1;for(int i=0;i<A.length;i++){if(A[i]<=A.length && A[i]>0 && A[A[i]-1]!=A[i])//这里A[A[i]-1]!=A[i]这个限制条件的意思是,已经满足条件的就不交换了{int temp=A[A[i]-1];A[A[i]-1]=A[i];A[i]=temp;i–;}}for(int i=0;i<A.length;i++){if(A[i]!=(i+1))return i+1;}return A.length+1;}}
版权声明:本文为博主原创文章,转载注明出处
最可怕的敌人,就是没有坚强的信念。