First Missing Positive

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

    For example,
    Given return 3,
    and [3,4,-1,1] return 2.

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

    容易想到的方案是先排序，然后遍历求得缺的最小整数。排序算法中常用的基于比较的方法时间复杂度的理论下界为 O(n \log n), 不符题目要求。常见的能达到线性时间复杂度的排序算法有 基数排序， 和 桶排序。

    设想我们对给定数组使用桶排序的思想排序，第一个桶放1，第二个桶放2，如果找不到相应的数，则相应的桶的值不变(可能为负值，也可能为其他值)。

    那么怎么才能做到原地排序呢？即若 A[i] = x, 则将 x 放到它该去的地方 - A[x - 1] = x, 同时将原来 A[x - 1] 地方的值交换给 A[i].

    排好序后遍历桶，如果不满足 f[i] = i + 1, 那么警察叔叔就是它了！如果都满足条件怎么办？那就返回给定数组大小再加1呗。

    核心代码为那几行交换，但是要很好地处理各种边界条件则要下一番功夫了，要能正常的交换，需满足以下几个条件：

    1. 为正数，负数和零都无法在桶中找到生存空间…
    2. A[i] != i + 1, 已满足条件了无需交换。
    3. A[i] != A[A[i] - 1], 避免欲交换的值和自身相同，否则有重复值时会产生死循环。

    注意交换的写法，若写成

    这又是满满的 bug :( 因为在第三行中A[i]已不再是之前的值，第二行赋值时已经改变，故源码中的写法比较安全。

    最后遍历桶排序后的数组，若在数组大小范围内找到不满足条件的解，直接返回，否则就意味着原数组给的元素都是从1开始的连续正整数，返回数组大小加1即可。

    「桶排序」需要遍历一次原数组，考虑到while循环也需要一定次数的遍历，故时间复杂度至少为 O(n). 最后求索引值最多遍历一次排序后数组，时间复杂度最高为 O(n), 用到了作为中间交换变量，空间复杂度为 O(1).