First Missing Positive

Given an unsorted integer array, find the firstmissing positive integer.

Have you met this question in a real interview? 

Yes

Example

Given [1,2,0] return 3, and [3,4,-1,1] return2.

Challenge

Your algorithm should run in O(n) time and uses constant space.

public class Solution {

    /**    

     * @param A: an array of integers

     * @return: an integer

     */

    public int firstMissingPositive(int[] A) {

        // write your code here    

        if(A.length == 0) return 1;

        for(int i = 0; i < A.length; i++){

            if(A[i] > 0 && A[i] <= A.length && A[i] != i+1 && A[i] != A[A[i]-1]){

                int temp = A[i];

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

                A[temp-1] = temp;

                i--;

            }

        }

        

        for(int i = 0; i < A.length; i++){

            if(A[i] != i+1){

                return i+1;

            }

        }

        return A.length+1;

    }

}