题解 | #数组中未出现的最小正整数#

原地哈希

（1）答案肯定在[1, n + 1]之间；
（2）通过原地哈希，将[1, n]的元素对应回数组的[0, n - 1]位置上；
时间复杂度：
空间复杂度：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i ++){
            //在整个外部for循环下，while的swap交换总次数最多为n次，所以时间复杂度为外部for循环的时间复杂度
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){ //没有在合适的位置
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for(int i = 0; i < n; i ++){
            if(nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};