Skip to main content

缺失的第一个正数

给你一个未排序的整数数组 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 没有出现。

简单做法：转Set,再从1开始递增判断

进阶做法：利用数组本身的索引作为“哈希表”，通过原地交换将正整数放到其对应的位置，再遍历查找缺失的最小正整数。

核心思路​

最小的正整数一定在 1 到 n+1 之间（n 是数组长度）：

  • 若数组包含 1~n 的所有正整数，则答案是 n+1；
  • 否则，答案是 1~n 中缺失的那个最小正整数。

因此，我们可以通过原地交换，将每个正整数 x 放到索引 x-1 的位置（即 nums[x-1] = x），然后遍历数组，找到第一个不满足 nums[i] = i+1 的位置，其对应的 i+1 就是答案。

具体步骤​

  1. 原地交换正整数：
    遍历数组，对每个元素 nums[i]：

    • 若 nums[i] 是正整数（1 ≤ nums[i] ≤ n），且它对应的位置 nums[i]-1 上的元素不是 nums[i]，则交换 nums[i] 和 nums[nums[i]-1]，直到 nums[i] 不在有效范围或已放到正确位置。

  2. 查找缺失的最小正整数：
    再次遍历数组，若 nums[i] ≠ i+1，则 i+1 是缺失的最小正整数。若所有位置都满足 nums[i] = i+1，则答案是 n+1。

代码实现​

function firstMissingPositive(nums) {
    const n = nums.length;
    
    // 第一步：将正整数放到正确的位置（nums[x-1] = x）
    for (let i = 0; i < n; i++) {
        // 仅处理 1~n 范围内的正整数，且避免重复交换（如 nums[i] 已在正确位置）
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            // 交换 nums[i] 和 nums[nums[i]-1]
            const x = nums[i];
            [nums[i], nums[x - 1]] = [nums[x - 1], nums[i]];
        }
    }
    
    // 第二步：查找第一个缺失的正整数
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    
    // 若 1~n 都存在，返回 n+1
    return n + 1;
}

示例分析​

以 nums = [3, 4, -1, 1] 为例（n=4）：

第一步：原地交换​

  • i=0，nums[0]=3（1≤3≤4），需放到索引 2（3-1）。交换后数组变为 [-1, 4, 3, 1]。
  • i=0 现在是 -1（无需处理），移动到 i=1。
  • i=1，nums[1]=4（1≤4≤4），需放到索引 3（4-1）。交换后数组变为 [-1, 1, 3, 4]。
  • i=1 现在是 1（1≤1≤4），需放到索引 0（1-1）。交换后数组变为 [1, -1, 3, 4]。
  • i=1 现在是 -1（无需处理），后续 i=2 和 i=3 已在正确位置（nums[2]=3，nums[3]=4）。

第二步：查找缺失值​

遍历数组：

  • i=0：nums[0]=1（符合 i+1=1）。
  • i=1：nums[1]=-1（不符合 i+1=2），因此返回 2。

复杂度分析​

  • 时间复杂度：O(n)。每个元素最多被交换一次（放到正确位置后不再移动），因此整体遍历次数为 O(n)。
  • 空间复杂度：O(1)。仅使用常数级额外空间，所有操作在原数组上进行。

边界情况验证​

  • 数组全为负数：[-3, -2] → 答案是 1（1 不在数组中）。
  • 数组包含 1~n 所有正整数：[1, 2, 3] → 答案是 4（n+1=3+1=4）。
  • 数组有重复元素：[2, 2] → 交换后 [2, 2]，i=0 时 nums[0]≠1，答案是 1。

这种方法通过“索引映射”巧妙利用数组本身存储信息，在不使用额外空间的情况下实现了线性时间复杂度，是解决该问题的最优解。