41. 缺失的第一个正整数#

生活中的算法#

想象你是一位图书馆管理员，正在整理一排连续编号的图书。这些书应该从1号开始按顺序排列，但是有些编号的书不见了。你的任务是找出第一个缺失的编号。这就像是在做点名，发现第一个没来上课的同学。

这个场景在生活中很常见。比如：

餐厅服务员查看哪个桌号是第一个空位
停车场管理员寻找第一个空闲的车位号
学校给新生分配第一个未使用的学号
医院为病人安排第一个可用的就诊序号

问题描述#

题目目标#

LeetCode第41题”缺失的第一个正整数”是这样描述的：给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1#

输入： nums = [3,4,-1,1] 输出： 2 说明： 数组中有1，3，4，所以第一个缺失的正整数是2。

示例 2#

输入： nums = [7,8,9,11,12] 输出： 1 说明： 数组中没有1，所以缺失的第一个正整数是1。

最直观的解法：排序后遍历#

就像整理图书时，先把所有的书按编号排好序，然后从1开始检查，看哪个编号最先空缺。

让我们用一个简单的例子来理解：

原数组：[3,1,4,-1]
1. 先排序（只考虑正数）：[1,3,4]
2. 从1开始检查：
   - 1存在
   - 2不存在，找到答案！

plaintext

优化解法：原地标记#

仔细思考会发现一个关键点：如果数组长度为n，那么答案一定在[1, n+1]范围内。就像有10个学生的班级，第一个缺席的学号最大不会超过11。

我们可以把数组本身作为标记板，把每个数放到它应该在的位置上（就像把每本书放到对应的编号位置）。

原地标记的原理#

把每个在[1,n]范围内的数x放到索引x-1的位置
再次遍历，第一个不在对应位置的数就指示了缺失的最小正整数这就像是：

先把每本书放到它编号对应的书架位置
然后从1号位置开始检查，找到第一个空位置

示例演示#

用nums = [3,4,-1,1]来说明：

1. 开始移动元素：
   [3,4,-1,1] 把3放到索引2
   [3,4,3,1] 把4放到索引3
   [3,1,3,4] 把1放到索引0
   [1,3,3,4]

2. 再次遍历，检查每个位置：
   位置0：期望1，实际1，正确
   位置1：期望2，实际3，找到答案2！

plaintext

Java代码实现#

public int firstMissingPositive(int[] nums) {
    // n 表示数组长度，答案一定在 [1, n+1] 范围内
    int n = nums.length;

    // 第一轮：把每个“有效正整数 x（1<=x<=n）”放到下标 x-1 的位置
    // 目标是尽可能构造成 nums[i] == i+1 的形式
    for (int i = 0; i < n; i++) {
        // 用 while 而不是 if：因为一次交换后，nums[i] 可能仍是可交换的有效值，需要继续归位
        // 交换条件说明：
        // 1) nums[i] > 0：只关心正整数
        // 2) nums[i] <= n：只关心可能影响答案范围的值
        // 3) nums[i] != nums[nums[i] - 1]：目标位不是同值，避免重复值导致死循环
        while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
            // 目标位置是 nums[i]-1，把当前值交换到它应该在的位置
            int temp = nums[nums[i] - 1];
            // 将当前值放到目标位置
            nums[nums[i] - 1] = nums[i];
            // 把目标位置原来的值放回当前位置，继续下一轮判断
            nums[i] = temp;
        }
    }

    // 第二轮：从左到右找第一个“值与下标不匹配”的位置
    // 理想状态应满足 nums[i] == i+1
    for (int i = 0; i < n; i++) {
        // 一旦不匹配，说明数字 i+1 缺失
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    // 若 1..n 都存在，则最小缺失正整数只能是 n+1
    return n + 1;
}

java

解法比较#

让我们比较这两种方法：

排序后遍历：

时间复杂度：O(nlogn)
空间复杂度：O(1)
优点：思路直观，易于理解
缺点：不满足时间复杂度要求

原地标记：

时间复杂度：O(n)
空间复杂度：O(1)
优点：满足所有要求，不需要额外空间
缺点：实现略微复杂，需要仔细处理边界情况

解题技巧总结#

这道题给我们的启示：

思考数据的取值范围很重要
有时候可以把数组本身当作标记数组使用
位置和值的对应关系常常能带来灵感
不要害怕修改原数组，有时这是提高效率的关键

类似的问题还有：

数组中重复的数字
找到所有数组中消失的数字
寻找重复数

小结#

通过缺失的第一个正整数这道题，我们学会了一个重要的思维方式：有时候看似需要额外空间的问题，可以通过巧妙利用输入数组本身来解决。这种思维不仅在这道题中有用，在处理其他需要标记或计数的问题时也很有启发。记住，当遇到需要找寻特定范围内缺失数字的问题时，考虑能否利用数组本身来存储信息！