41. First Missing Positive.md

41. First Missing Positive

思路

题目要求找到缺失的首个正数。要求时间复杂度O(n)空间复杂度O(1)。

思路一、nums数组只读

提示告诉我们先不考虑额外的空间，那我们就可以用一个大小为n+1的bool数组bucket，bucket[i] = true表示原数组中存在 i，所以我们只需要遍历一遍原数组来填充bucket数组然后再从前往后遍历bucket，一旦遇到bucket[i] = false那么返回i即可。

时间复杂度O(n)空间复杂度O(n)，空间复杂度没有达到要求，但这种方法的好处是不用修改原数组，所以如果原数组是只读的那这种方法还是不错的。

思路二

我们考虑将思路二中的额外bucket数组用原数组代替，即在nums[i]存放i（实际代码中存放的是i+1）。为此我们可以从前往后遍历数组，一旦遇到

nums[i] > 0 && nums[i] < n && nums[i] != nums[nums[i] - 1]

那么就不断交换nums[i]和nums[nums[i] - 1]直到上述条件不满足。

由于每一次swap都会使有一个元素落在最终位置，所以最多交换n次，所以时间复杂度为O(n)，没有使用额外的空间，所以空间复杂度O(1)。

C++

思路一

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        vector<bool>bucket(n + 1, false);
        
        for(int num: nums)
            if(num > 0 && num <= n) bucket[num] = true;
        
        for(int i = 1; i <= n; i++)
            if(!bucket[i]) return i;
        
        return n + 1;
    }
};

思路二

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        for(int i = 0; i < n; i++){
            while(nums[i] > 0 && nums[i] < n && nums[i] != nums[nums[i] - 1])
                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;
    }
};