[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.

解题思路：
  1. 长度为n的数组应该包含的正整数是1-n. 而数组的index为0-n-1。 所以我们可以将数为i的数移到i-1的位置上。这样，第一个A[i-1] != i的数，就是我们要找的first missing positive

注意：当我们移动数i到i-1的位置上时，要考虑到i必须在1-n之间，并且i-1位置原有的数不为i

public int firstMissingPositive(int[] A) {
       for(int i = 0 ; i < A.length; i++){
           while(A[i] > 0 && A[i] <= A.length && A[A[i] - 1] != A[i]){
               int tmp = A[A[i]-1];
               A[A[i]-1] = A[i]; 
               A[i] = tmp;
           }
       }
       
       int i = 1;
       while (i <= A.length && A[i-1] == i){
           i++;
       }
       
       return i;
    }