41. 缺失的第一个正数

难度：🔴 Hard | 标签：原地哈希、数组 | 状态：⬜ LeetCode 链接

思路

O(n) 时间 + O(1) 空间，必须用原地哈希：把 nums[i] 放到下标 nums[i] - 1 的位置。 答案落在 [1, n+1] 区间。扫第二遍，第一个 nums[i] != i+1 的 i+1 即答案；都对则答案是 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[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;
    }
};

复杂度

• 时间 O(n)，空间 O(1)
• 看似双层循环，每次 swap 都让一个数归位，总 swap 次数 ≤ n

易错 / 回顾

• swap 条件 nums[nums[i]-1] != nums[i]，否则相同值死循环
• 先检查 nums[i] > 0 && nums[i] <= n，越界直接跳
• 用 while 不是 if：一次 swap 可能换来另一个需要归位的数