首页 > 代码库 > First Missing Positive
First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0]
return 3
,
and [3,4,-1,1]
return 2
.
Your algorithm should run in O(n) time and uses constant space.
开始没有想到这个思路,参考网上的例子才有这个思路
思路:交换数组元素,使得数组中第i位存放数值(i+1)。最后遍历数组,寻找第一个不符合此要求的元素,返回其下标。整个过程需要遍历两次数组,复杂度为O(n)。
然后在复杂度这卡了一下,由于每次交换一定有一个元素在正确的位置,在下一次判断是否交换的时候由于这个元素已经在正确的位置所以不交换,因此保证最多交换n次,然后遍历数组,找出第一个不符合要求的元素,最多找n个位置。因此,复杂度为O(n)
public int firstMissingPositive(int[] A) { for(int i=0;i<A.length;i++){ if(i>=0&&i<A.length&&A[i]!=i+1){ if(A[i]-1>=A.length||A[i]-1<0||A[A[i]-1]==A[i]){ A[i] = -1; }else{ int temp = A[A[i]-1]; A[A[i]-1] = A[i]; A[i] = temp; i--; } } } int i=0; for(i=0;i<A.length;i++){ if(i+1!=A[i]){ break; } } return i+1; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。