缺失的第一个正数

LeetCode 官方题目链接

1. 题目呈现

难度等级：🔴 困难
核心考察点：数组、哈希表（原地哈希）

给你一个未排序的整数数组 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

2. 解题思路拆解

方法：原地哈希 (In-place Hashing)

这道题的难点在于：时间复杂度 O(n) 且 空间复杂度 O(1)。通常查找是否存在需要用哈希表（空间 O(n)）或者排序（时间 O(n log n)）。既然题目限制了这两点，说明我们需要利用数组本身作为哈希表。

核心观察：
- 如果数组长度为 n，那么“缺失的第一个正数”一定在 [1, n+1] 这个范围内。
- 举例：数组长度 3。可能情况 [1,2,3] -> 缺失 4；[100, 200, 300] -> 缺失 1。
- 所以，我们只需要关注 [1, n] 范围内的数字。
映射规则：
- 我们可以尝试把数值 x 放到下标为 x-1 的位置上。
- 即：数值 1 放在 nums[0]，数值 2 放在 nums[1]，...，数值 k 放在 nums[k-1]。
算法流程：
- 遍历交换：遍历数组，如果当前元素 nums[i] 是一个在 [1, n] 范围内的正数，且它没有在正确的位置上（即 nums[i] !== nums[nums[i]-1]），就把它交换到正确的位置上去。
  - 注意：交换过来的新元素可能也需要继续交换，所以这里要用 while 循环。
- 再次遍历查找：交换完成后，数组应该大致有序了（比如 [1, 2, 3, -1, 5]）。我们从头遍历，第一个满足 nums[i] !== i + 1 的位置 i，其对应的 i + 1 就是缺失的第一个正数。
- 兜底：如果遍历完都满足，说明数组是 [1, 2, ..., n]，那么缺失的就是 n + 1。

3. 代码实现

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        // 核心逻辑：
        // 1. nums[i] 必须是正数 (nums[i] > 0)
        // 2. nums[i] 必须在数组索引范围内 (nums[i] <= n)
        // 3. nums[i] 还没有放在正确的位置上 (nums[nums[i] - 1] !== nums[i])
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            // 交换 nums[i] 和 nums[nums[i] - 1]
            const temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    
    // 检查第一个不符合 nums[i] == i + 1 的位置
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    
    // 如果都符合，说明是 [1, 2, ..., n]，缺失的是 n + 1
    return n + 1;
};

代码执行演示

输入 nums = [3, 4, -1, 1], n = 4

i = 0, nums[0] = 3:
- 3 在范围内，且 nums[2] (-1) != 3。
- 交换 3 和 -1。数组变 [-1, 4, 3, 1]。
- 现在 nums[0] = -1，不满足 > 0，停止。
i = 1, nums[1] = 4:
- 4 在范围内，且 nums[3] (1) != 4。
- 交换 4 和 1。数组变 [-1, 1, 3, 4]。
- 现在 nums[1] = 1。
- 1 在范围内，且 nums[0] (-1) != 1。
- 交换 1 和 -1。数组变 [1, -1, 3, 4]。
- 现在 nums[1] = -1，不满足 > 0，停止。
i = 2, nums[2] = 3:
- 3 在范围内，且 nums[2] (3) == 3。位置正确，无需交换。
i = 3, nums[3] = 4:
- 4 在范围内，且 nums[3] (4) == 4。位置正确，无需交换。

最终数组：[1, -1, 3, 4]

查找缺失：

i = 0: nums[0] = 1，0 + 1 = 1。匹配。
i = 1: nums[1] = -1，1 + 1 = 2。不匹配！
返回 2。

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。虽然有 `while` 循环，但每个元素最多被交换一次到正确的位置上，所以总的操作次数是线性的。
空间复杂度	$O(1)$。原地修改数组，不需要额外空间。

缺失的第一个正数 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：原地哈希 (In-place Hashing) ​

3. 代码实现 ​

代码执行演示 ​