040. First Missing Positive

这道题，能把题意看明白，就很不容易了。

 1,2,0     ->  0,1,2,3     ->  size == 3
                     ^
 3,4,-1,1  ->  -1,1,2,3,4  ->  size == 4
                    ^  

按照上述排列方式，就能很清晰的看出，First Missing Positive 的含义。这个数有如下几个条件：

• 最大为 n+1. (想象第一个例子，极端情况为 1,2,3, 那么 result 即为 4, 恰为 n+1)
• 最小为 1.
• 1 ~ n+1 中间，第一个缺的数，即为返回结果。(容易理解，如果 1~n 都没有缺的，那么结果一定是 n+1 了)

所以问题来了，怎么能在一次迭代中找出缺的那个？想象我们大脑是如何一下子看出来的？嗯，排列。

但排列完，就已经耗费了 O(N)，又要花 O(N) 去确认缺的那个数。其实，我们真的是排完序才知道空缺吗？显然不是。

另外，这道题要求不能用额外的空间，即使往排序上想，也只能想着如何 swap 了。

---

一般的排序，的确是比较复杂的。但仔细观察这道题，能够发现这个"排序"却比较特殊，首先它是从 1 开始的，且连续。

这让我们想到了神马？没错，像序号，就如数据库表的自增主键一样！那么找到缺的，岂不是一眼就看出来了？

如何能让这个无序的数组，看起来像序号一样呢？而且手段只有 swap. 有了，序号我们是知道的啊，这样 swap 就有明确的目的了。

 index:  1, 2, 3, 4
 array:  3, 4,-1, 1
         ^     ^    --- swap(3,-1)
        -1, 4, 3, 1
            ^     ^ --- swap(4, 1)
        -1, 1, 3, 4
         ^  ^       --- swap(1,-1)
         1,-1, 3, 4
            ^

经过几步 swap, 我们惊人的发现最终对不齐的那个序号（2 : -1）就是我们要的结果！我们尝试用代码描述上述过程：

for (int i=0; i<n; ++i)
     while (A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1]) // 前两个条件限定范围，最后是如果序号位置的值与当前值一样，交换无意义
          swap(A[i], A[A[i]-1]);
for (int i=0; i<n; ++i)
     if (A[i] != i+1) return i+1; // 最后的检查，一旦发现与序号不符，立刻返回
return n+1; // 如果都相符，那么返回 n+1

6行，提交，最高效率 AC.(4ms)