First Missing Position

题目：

Given an unsorted integer array, find the first missing positive integer.

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

分析：

这题目里面这个swap程序实在是有点坏啊~因为A[i]是后面A[A[i] - 1]index的一部分，所以先后顺序是很有讲究的

其实题目涉及到桶排序原理的问题还是挺厉害的，就过一遍，把现有的位置都放上数字，然后查查第一个有问题的位置在哪里就可以了。

桶排序在uniform distribution的情况下O(n)因为他并不是基于比较的排序

解法：

class Solution {
public:
    /**    
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        if (A.size() == 0) {
            return 1;
        }
        for (int i = 0; i < A.size(); i++) {

            while (A[i] != (i + 1) && A[i] > 0 && A[i] < A.size() ) {
                if (A[i] == A[A[i] - 1]) {
                    break;
                }
                int temp = A[A[i] - 1];
                A[A[i] - 1] = A[i];
                A[i] = temp;
                // 陷阱，先后顺序有讲究的
                /*
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
                */
            }

        }

        for (int i = 0; i < A.size(); i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }

        return A.size() + 1;
    }
};