【LeetCode热题100道笔记】缺失的第一个正数

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1

思考一

先计算数组中的最大的数 maxNum，若最大数小于等于 0，则 maxNum = 1，否则为数组中最大的正整数。用哈希表存储数组中每个数，然后从[1,maxNum+1]中寻找数组不存在的最小正整数，用哈希表判断当前遍历的数是否存在。时间复杂度 $O(n)$，空间复杂度 $O(n)$。由于题目要求使用常数级额外空间，因此当前实现不满足要求。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    const set = new Set();
    let maxNum = 0;
    for (let num of nums) {
        maxNum = Math.max(maxNum, num);
        set.add(num);
    }
    if (maxNum < nums.length) {
        maxNum = nums.length;
    }

    for (let i = 1; i <= maxNum + 1; i++) {
        if (set.has(i)) continue;
        return i;
    }
};

思考二

要满足常数级常数级额外空间的要求，我们可以利用数组本身作为哈希表来标记元素的存在状态，核心思路是将值为x的元素放到索引x-1的位置上，然后检查第一个不匹配的索引 + 1 即为结果。

算法过程

1. 置换阶段：遍历数组，将每个值为x（1 ≤ x ≤ n）的元素交换到索引x-1的位置，确保"值"与"索引+1"对应
2. 检查阶段：再次遍历数组，第一个不满足nums[i] === i+1的位置i，其i+1就是缺失的最小正整数
3. 边界情况：如果所有位置都匹配，则缺失的是n+1

复杂度分析

• 时间复杂度：O(n)，每个元素最多被交换两次，整体仍是线性时间
• 空间复杂度：O(1)，仅使用常数级额外空间

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    const n = nums.length;
    
    // 第一步：将每个正数放到正确的位置上
    for (let i = 0; i < n; i++) {
        // 只有当当前数字是正数且在有效范围内，并且没有放在正确位置时才交换
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            // 将nums[i]放到索引为nums[i]-1的位置
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }
    
    // 第二步：检查哪个位置没有对应的正数
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    
    // 所有位置都正确，则缺失的是n+1
    return n + 1;
};