[41] 缺失的第一个正数

要找到缺失的第一个正数，可以利用数组的索引进行原地哈希。这个方法的时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。算法的核心思想是把每个正数 $x$ 放在数组的第 $x-1$ 个位置上。这样最终数组中每个位置上存储的数值就是该位置的索引加 1。如果某个位置上不是期望的数值，那么这个位置的索引加 1 就是缺失的第一个正数。

算法步骤

1. 遍历数组：将每个正数 $x$ 放在数组的第 $x-1$ 个位置上。如果 $x$ 超出数组范围或者已经在正确位置上，则跳过。
2. 再次遍历数组：检查每个位置 $i$ 是否存储了 $i+1$。
3. 返回结果：如果发现第一个位置 $i$ 上的数值不是 $i+1$，则返回 $i+1$。如果所有位置都正确，则返回 $n+1$。

实现代码

var firstMissingPositive = function (nums) {
    const n = nums.length;

    // 把每个正数 x 放到位置 x-1 上
    for (let i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }

    // 查找第一个位置 i 上不是 i+1 的数
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    // 如果都正确，返回 n+1
    return n + 1;
};

// 测试用例
console.log(firstMissingPositive([1, 2, 0])); // 输出: 3
console.log(firstMissingPositive([3, 4, -1, 1])); // 输出: 2
console.log(firstMissingPositive([7, 8, 9, 11, 12])); // 输出: 1

解释

1. 遍历数组进行哈希：通过 while 循环将每个正数 $x$ 放在数组的第 $x-1$ 个位置上。利用交换操作来实现这一点。这个步骤会将数组中的正数按照其值调整到正确的位置上。
2. 再次遍历数组：检查每个位置 $i$ 上的值是否等于 $i+1$。如果发现第一个位置 $i$ 上的数值不是 $i+1$，则 $i+1$ 就是缺失的第一个正数。
3. 返回结果：如果所有位置都正确，则返回 $n+1$。

这种方法的优势在于只需要常数空间，而且时间复杂度是线性的，非常高效。