Find the Missing Positive Integer -- LeetCode 41

[Question]:

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.

[Analysis]:

Think of an array A, where A[i] = i. It is easy to spot the integer if there is one missing. It is a case of bucket sort - make each bucket i contain itself.

Scan the array A, use bucket sort, place each A[i] in its bucket position if A[i] is within the range of 0.. A.length-1. Then go through A[i] find the first integer i, where i!=A[i]. That is the answer.

[Solution]:
//--- in C++ ---
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i=0; i<nums.size(); ) {
            int& v = nums[i];
            if (v-1>=0 && v-1< nums.size() && v-1!=i && v!=nums[v-1] ) {
                swap (v, nums[v-1]);
            }
            else i++;
        }
        for (int i=0; i<nums.size(); i++)
            if (nums[i]-1!=i) return 1+i;
        return nums.size()+1;
    }
};

//--- in Java ---
public class Solution {
    public int firstMissingPositive(int[] A) {

        if (A.length == 0) return 1;
     
        int i=0;
        while (i<A.length) {
            if (A[i]>=0 && A[i]<A.length) {
                if (A[i]!=i && A[i]!=A[A[i]]) {
                    int temp = A[A[i]];
                    A[A[i]] = A[i];
                    A[i] = temp;
                    continue;
                }
            }
            i++;
        }
     
        for (i=1; i<A.length; i++) {
            if (i!=A[i]) return i;
        }
     
        if (A[0]==A.length) return A.length+1;
     
        return A.length;
    }
}