firstMissPositive

41. 缺失的第一个正数

分析

原地哈希：
- 对于一个长度为 n 的数组，最小的缺失正整数只能在 1 到 n+1 之间
- 遍历数组，对于每个数字 nums[i]，如果满足条件 1 ≤ nums[i] ≤ n 且 nums[i] != nums[nums[i] - 1]，则将其交换到正确的位置
- 通过循环交换，可以在原地调整数组顺序
检查缺失：
- 调整完成后，遍历数组，检查每个位置是否满足 nums[i] == i + 1
- 如果存在不满足的位置，则返回 i + 1
- 如果所有位置都满足，说明数组包含所有 1 到 n 的正整数，缺失的正整数为 n + 1

时间复杂度

每个数字最多只会被交换一次，因此总操作次数为 O(n)

空间复杂度

原地调整数组，无额外空间开销，空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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[i] != nums[nums[i] - 1])
                std::swap(nums[i], nums[nums[i] - 1]);

        // 查找第一个缺失的正整数
        for (int i = 0; i < n; ++i)
            if (nums[i] != i + 1)
                return i + 1;

        // 如果所有正整数都在正确位置，返回 n + 1
        return n + 1;
    }
};