LeetCode-Hot100：缺失的第一个正数

题目

暴力

思路：从 1 开始枚举正整数，逐个遍历数组判断是否存在，返回第一个不存在的数。

class SolutionBrute {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int x = 1; x <= n + 1; ++x) {
            bool found = false;

            for (int num : nums) {
                if (num == x) {
                    found = true;
                    break;
                }
            }

            if (!found) return x;
        }

        return n + 1;
    }
};

时间复杂度：O(n²)
空间复杂度：O(1)

优化

思路：用哈希集合记录数组中的元素，再从 1 到 n + 1 查找第一个未出现的正整数。

class SolutionHash {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int n = nums.size();

        for (int x = 1; x <= n + 1; ++x) {
            if (!s.count(x)) return x;
        }

        return n + 1;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

最优

思路：将合法数字 x 放到下标 x - 1 的位置，整理后扫描数组，首个位置不满足 nums[i] == i + 1 时，i + 1 即为答案。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            while (
                nums[i] >= 1 &&
                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;
    }
};