[LeetCode] First Missing Positive

Problem:

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.

Solution:O(n)

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

Key Concept: Find a suitable to swap