LeetCode 41. 缺失的第一个正数

2026-06-16 HGNULB 约 4 分钟

文章信息 20 个分类 3 个标签

分类

LeetCode CodeTop 困难未解决 100-200 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东拼多多网易虾皮哔哩哔哩 LeetCode 热题 100

题目描述

✅ 41. 缺失的第一个正数

题意分析

给定一个未排序的整数数组，找出其中没有出现的最小正整数。数组里可能混有负数、零、重复值和远超数组长度的大数，这些都是干扰项。

进阶要求是硬约束：$O(n)$ 时间加常数级额外空间。排序要 $O(n \log n)$，过不了时间要求；哈希表能做到 $O(n)$ 时间，但要 $O(n)$ 额外空间。两条常规路都被堵死，这正是题目被标为困难的原因。

关键的界：长度为 n 的数组最多装下 n 个互不相同的值。若 1..n 全部出现，答案就是 n + 1；否则答案是 1..n 中缺失的最小者。也就是说答案必然落在 [1, n + 1] 内，所有 <= 0 或 > n 的值都与答案无关。

边界情况：全是负数或零时答案是 1；单元素 [1] 答案是 2。

解法：原地交换归位

核心思路

长度为 n 的数组中，答案一定在 [1, n + 1]。把数组下标当作哈希桶：值 x 应放在下标 x - 1。

通过交换将 [1, n] 内的数归位，再从左到右查找第一个 nums[i] != i + 1 的位置；若全部匹配，答案就是 n + 1。

解题步骤

遍历数组，对每个位置反复检查当前值。

若 nums[i] 在 [1, n] 内且目标位置不是同一个值，就将它交换到 nums[i] - 1。

归位结束后再次扫描，返回第一个下标与值不匹配的位置。

若 1 到 n 都已归位，返回 n + 1。

代码实现

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int target = nums[i] - 1;
                int temp = nums[target];
                nums[target] = nums[i];
                nums[i] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            target := nums[i] - 1
            nums[target], nums[i] = nums[i], nums[target]
        }
    }

    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }
    return n + 1
}

复杂度分析

时间复杂度：$O(n)$，每次交换至少让一个值归位，总交换次数不超过 n。

空间复杂度：$O(1)$，直接修改输入数组。

关键点总结

只需归位 [1, n] 内的值，其他值不可能影响答案。

交换要使用 while，继续处理被换到当前位置的新值。

目标位置已有相同值时必须停止，避免重复值导致死循环。

易错点总结

交换前必须检查值的范围，否则目标下标可能越界。

缺少重复值判断时，两个相同元素会无限交换。

只交换一次会漏掉被换回来的、仍需归位的值。

最终返回的是 i + 1；全部匹配时返回 n + 1。

相似题目

题目	难度	考察点
268. 丢失的数字	简单	值域固定为 `[0, n]`，异或或求和即可，无需归位
287. 寻找重复数	中等	禁止修改数组，转化为链表找环
442. 数组中重复的数据	中等	用取负号原地标记，找出所有出现两次的数
448. 找到所有数组中消失的数字	简单	原地标记的对偶问题，找出所有缺失的数
645. 错误的集合	简单	一个重复与一个缺失需要同时定位
765. 情侣牵手	困难	在置换环上用最少交换次数完成归位