First Missing Positive (C++ code)

LeetCode First Missing Positive, Mar 8 '12

 难度5，出现频率2

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.
 52741
思路：一共n个数，所以first missing positive最大为n+1.从头检查每个数，如果该数i满足1<=i<=n,则把该数放在a[i-1]里。这样放完后再检查一遍，当遇到a[i] != i+1，return i+1。如果a[i] = i+1 for 0<=i<=n-1,则返回n+1.

int firstMissingPositive(int A[], int n) {
   int i;
  for(i = 0; i < n; i++){
         int temp = A[i];

    while( temp <= n && temp >= 1 && temp != i + 1 && A[temp-1] != temp){

         A[i] = A[A[i] - 1];

         A[temp-1] = temp;
       
         temp = A[i];
       

    }

  }

  for(i = 0; i < n; i++){

    if(A[i] != i + 1) return i+1;

  }

  return n+1;



}