[LeetCode]First Missing Positive

要求constant space，不能用数据结构存之前的数据从而不断更新结果。所以我们尝试操作原数组，假设数组size为n，我们只要把正整数i放在index为i - 1的地方，就相当于用map标记了这个数出现过，之后我们从左往右扫第一个不match的数就是我们要的答案。要达成这个目的我们只需要确定i的数在[1,n]的范围，nums[i] != i + 1的情况下，每次把nums[i]和nums[nums[i]]的数交换，注意如果两者相等就别换了，会陷入无限循环，这样只要数组充存在[1,n]的数，它就会被换到所在的位置。时间复杂第O(n)，常数空间，代码如下：

这道题的做法可以给我们其他的题一些思路，当input的范围在一个连续的区间且区间长度和input数组长度接近时，我们可以modify原数组来当做一个map。