[LintCode] #189 First Missing Positive

http://www.lintcode.com/en/problem/first-missing-positive/

http://www.cnblogs.com/yuzhangcmu/p/4200096.html

public class Solution {
    /**    
     * @param A: an array of integers
     * @return: an integer
     */
    public static int firstMissingPositive(int[] A) {
        // write your code here    
        if (A == null || A.length == 0) {
            return 1;
        }
        for (int i = 0; i < A.length; i++) {
            while (A[i] - 1 < A.length && A[i] - 1 >= 0 && A[A[i] - 1] != A[i] ) {
                swap(A, i, A[i] - 1);
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        
        return A.length + 1;
    }
    
    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}