传送门

这题很巧妙的。

题意是这样的：一个长度为n的nums数组，在自然状态下这个数组内的成员应该是(1,2,3,…,n)，但现在这个数组被打乱并拿走了一些数，我们要做的就是找出nums中缺失的第一个正数。

题目要求时间复杂度O(n)，空间复杂度O(1)。

这是一道hard，刚刚拿到手的时候挺懵的，在查阅大佬题解后了解到了一种“hash碰撞法”，以下做思路转述。

首先，合法的元素应该∈[1,n]，所以非正数成员直接标记为非法。第一次遍历，对于每个合法的成员，我们把它与自己位置上当前的元素做交换。第二次遍历去找出第一个与自己下标不相等的成员，答案就是这个下标。如果遍历到尾都没找到这样的成员，则答案为n+1。

上述思路的正确性是显然地，因为它严谨地把每一个成员放到自己应该在的下标上了，如果出现下标与值不等的情况，说明数组中缺失了这个成员。那么我们所找到的第一个缺失的成员自然就是符合题意的答案。

不难分析出这个算法的时间复杂度是线性的，也符合要求。

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

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

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