LeetCode 补拙笔记

0. 前言

• 日期：2026.07.01
• 题目：41. 缺失的第一个正数
• 难度：困难
• 标签：数组、原地哈希、置换

1. 题目理解

问题描述 给定无序整数数组 nums，找出数组中未出现的最小正整数；进阶要求时间复杂度 $O(n)$、仅常数级额外空间。

示例

输入：nums = [1,2,0] 输出：3 解释：1、2 均存在，最小缺失正整数为3

输入：nums = [3,4,-1,1] 输出：2 解释：存在1，缺失2

输入：nums = [7,8,9,11,12] 输出：1 解释：1 未出现在数组中

2. 解题思路

核心观察

1. 答案范围一定在 [1, n+1]（n为数组长度）：若1~n全部存在则答案为n+1，否则是1~n中缺失的最小数；
2. 哈希集合原版：直接存储全部数字，从1开始遍历查找缺失值，但占用 $O(n)$ 空间，不满足进阶要求；
3. 原地置换优化（原地哈希）：把数字 x 放到下标 x-1 的位置，遍历后第一个不满足 nums[i] = i+1 的下标对应 i+1 即为答案，全程原地操作，无额外容器。

算法步骤

哈希集合原版：

1. 将数组所有元素存入哈希集合；
2. 从1开始依次判断集合是否包含当前数字，第一个不存在的数字直接返回。

原地置换优化版：

1. 遍历数组，将合法区间 [1,n] 的数字 x 交换到下标 x-1；
2. 循环交换直到当前数字不满足交换条件，避免死循环；
3. 二次遍历数组，找到首个 nums[i] != i+1，返回 i+1；
4. 全部匹配则返回 n+1。

3. 代码实现

package lc0_lc99.lc41;

import java.util.HashSet;

class Solution {
    public int firstMissingPositive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i : nums){
            set.add(i);
        }
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            if (!set.contains(i)){
                return i;
            }
        }
        return -1 ;
    }
}

4. 代码优化说明

class Solution {
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    // 原地置换，把x放到x-1下标
    for (int i = 0; i < n; i++) {
        // 仅处理1~n范围内、且目标位置数字不相等的元素，消除重复交换死循环
        while(nums[i] - 1 >= 0 && nums[i] - 1 < n && nums[i] != nums[nums[i] - 1]){
            swap(nums[i] - 1, i, nums);
        }
    }
    int i = 0;
    // 遍历找第一个不匹配的位置
    for (;i < n; i++){
        if (nums[i] != i + 1){
            return i + 1;
        }
    }
    // 1~n全部齐全，答案为n+1
    return i + 1;
}

    private void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

5. 复杂度分析

• 哈希集合原版 时间复杂度：$O(n)$，两次线性遍历；依赖哈希容器，存在装箱、查询开销 空间复杂度：$O(n)$，哈希集合存储全部数组元素，不满足常数空间要求
• 原地置换优化版 时间复杂度：$O(n)$，每个元素最多交换一次，总操作线性；无哈希容器分支 空间复杂度：$O(1)$，仅swap临时变量，原地修改原数组，符合进阶常数空间限制

6. 总结

• 核心：答案仅存在于 1~n+1，利用数组下标做原地哈希映射，规避额外存储空间；
• 优化亮点：舍弃哈希集合，原地置换完成数字归位，满足题目常数空间限制；通过while循环条件过滤无效数字，减少多余交换分支；
• 边界关键点：负数、大于数组长度的数字无需处理；重复数字需判断目标位置值避免死循环。