跳到主要内容

LeetCode 41. 缺失的第一个正数

本节目标

把值域与数组下标建立对应关系，用原地索引放置找到最小缺失正数。

这道题是数组与矩阵综合框架中的原地哈希母题。题目要求线性时间和常数额外空间，提示我们让数组位置本身承担集合记录职责。

查看原题

题意与约束​

给定一个未排序整数数组，返回其中没有出现的最小正整数。要求时间复杂度为 O(n)，额外空间复杂度为 O(1)。

第一反应：排序或哈希​

排序后从 1 开始扫描能够找到答案，但时间复杂度是 O(n log n)；把所有正数放入哈希集合可以在线性时间内查询，却需要 O(n) 额外空间。两种朴素方案分别违反了题目的时间或空间约束，瓶颈在于没有复用输入数组本身的位置。

缩小有效值域​

长度为 n 的数组至多包含 n 个不同正整数，因此答案一定在 [1, n + 1] 中。大于 n 的数、零和负数都不可能占据答案对应的位置。

于是可以建立映射：值 x 应放在下标 x - 1。

原地索引放置​

遍历每个位置，只要当前值满足：

  • 位于 [1, n]；
  • 目标位置上不是同一个值；

就把它交换到 nums[x - 1]。交换后当前位置得到新值，需要继续判断，因此这里使用 while 而不是单次 if。

第二次扫描时，第一个满足 nums[index] != index + 1 的位置就对应缺失答案。如果所有位置都正确，答案是 n + 1。

“目标位置值不同”这一条件非常重要：遇到重复值时继续交换会在两个相同数字之间无限循环。

代码实现​

两份实现都把数组重排为尽可能接近 [1, 2, ..., n] 的形式，再扫描第一个错位位置。

C++17
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        for (int index = 0; index < n; index++) {
            while (
                nums[index] >= 1 &&
                nums[index] <= n &&
                nums[nums[index] - 1] != nums[index]
            ) {
                swap(nums[index], nums[nums[index] - 1]);
            }
        }

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

复杂度分析​

  • 时间复杂度：O(n)。虽然包含 while，但每次有效交换都会把至少一个值放回目标位置，总交换次数为 O(n)。
  • 空间复杂度：O(1)，直接复用输入数组。

易错点​

  • 认为嵌套 while 必然是 O(n²)，忽略每次交换带来的单调进展。
  • 把不在 [1, n] 的值也当作下标。
  • 重复值已经占据目标位置时仍继续交换，造成死循环。
  • 第二次扫描返回下标而非正整数 index + 1。

模式迁移​

当值域与下标规模相近、允许修改输入且要求常数额外空间时，可以把数组视为原地哈希表。迁移时要先界定有效值域，并证明每次交换都会让某个值进入最终位置。