题解 | #缺失的第一个正整数#

解题思路

(数组,哈希表,原地交换) $O(1)O(1)$

如果没有空间限制的话，可以使用哈希表来解，先把所有元素放入哈希表 set 中，然后从 1 开始在哈希表中查询第一个未出现的正整数。

要求使用常数空间的话想到在原数组原地交换，而我们关心的是正数，所以如果 nums[i] 是正数 > 0 且 < n 且 nums[i] 的位置上不是当前数，就把他放到应该的位置上去（防止死循环，如果原来就在正确的位置上，一直交换）

每个正数 nums[i] 的位置在 nums[i] - 1 上，即 0 的位置上放 1，以此类推（因为数组的大小是 n，那如果出现 n 放在位置 n 上会越界）。

最后再遍历一遍数组，如果当前位置上的数 nums[i] 不等于 i + 1，则 i + 1 就是缺少的正整数。

如果遍历结束之后，还没有找到答案，说明所有数都在正确的位置上，是一个连续序列，那么答案就是 n + 1。

时间复杂度

$O(n)O(n)$

空间复杂度

$O(1)O(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;
    }
};