首页 > 代码库 > 【leetcode】 First Missing Positive
【leetcode】 First Missing Positive
【LeetCode】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.
找到第一个没有出现的正整数
思路:
http://tech-wonderland.net/blog/leetcode-first-missing-positive.html
就是把出现的正整数a都放在a-1的位置,然后从头开始历遍,发现A[i] != i + 1的情况就是所要的结果
当我们遍历数组的时候,如果我们发现A[i] != i,那么我们就swap(A[A[i]], A[i]),让A[i]放在正确的位置上。而对于交换之后的A[i],我们继续做这个操作,直至交换没有意义为止。没有意义表示当前数不是正数,或超过数组长度,或与A[A[i]]相等。我们不关心这些数被排在什么位置。此外还要考虑如果整个数组都是连续的正数,比如A[] = {1,2},经过我们上面的排序之后会变成{2, 1},因为A[1] == 1(从1开始对比),而A[2]超出范围,所以函数会认为2之前的都出现过了而2没有出现过,返回2。为了防止把正确的数"挤"出数组,我们让A[A[i]-1]与A[i]交换,然后比较i+1和A[i]。
代码如下:
1 class Solution { 2 public: 3 int firstMissingPositive(vector<int>& A) { 4 int n=A.size(); 5 int i=0,j; 6 while(i<n) 7 { 8 if(A[i]!=i+1&&A[i]>0&&A[i]<=n&&A[i]!=A[A[i]-1]) 9 swap(A[i],A[A[i]-1]); 10 else 11 i++; 12 } 13 for(j=0;j<n;++j) 14 if(A[j]!=j+1) 15 return j+1; 16 return n+1; 17 } 18 };
【leetcode】 First Missing Positive