Sign in Subscribe
算法

缺失的第一个正数

loser

• 6 min read
Share

给你一个未排序的整数数组 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
解释：最小的正数 1 没有出现。

提示：

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

原地哈希-置换：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n; i++)
        {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
            {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

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

        return n + 1;
    }
};

核心思想

这题要求：

  • 时间复杂度 O(n)
  • 额外空间复杂度 O(1)

所以不能排序，因为排序一般至少需要 O(n log n) 时间。

也不能用哈希集合记录所有出现过的正数，因为那会使用 O(n) 额外空间。

我们需要直接利用原数组本身来做“哈希表”。

这题最关键的观察是：

对于长度为 n 的数组，缺失的第一个正数一定在 [1, n + 1] 范围内。

因此我们只关心 1 ~ n 这些数。

如果数字 x 在 1 ~ n 范围内，那么它最理想的位置应该是：

下标 x - 1

也就是说：

  • 数字 1 应该放在下标 0
  • 数字 2 应该放在下标 1
  • 数字 3 应该放在下标 2
  • ...
  • 数字 n 应该放在下标 n - 1

所以我们可以不断交换元素，让每个合法数字尽量回到自己的位置。

最后再从左到右扫描。

第一个不满足：

nums[i] == i + 1

的位置，就说明 i + 1 没有出现。

为什么答案一定在 [1, n + 1]

数组长度是 n。

最理想的情况是：

1, 2, 3, ..., n

这 n 个正整数全部出现了。

那么缺失的第一个正数就是：

n + 1

如果 1 ~ n 中有任意一个数没有出现，那么缺失的第一个正数一定就在 1 ~ n 之间。

所以答案不可能超过 n + 1。

因此，我们只需要把 1 ~ n 范围内的数字放到正确位置。

小于等于 0 的数、以及大于 n 的数，都不会影响答案。

原地哈希怎么做

如果当前下标是 i，当前数字是：

nums[i] = x

并且满足：

1 <= x <= n

那么数字 x 应该去的位置是：

x - 1

所以可以把它和 nums[x - 1] 交换。

代码中写成：

swap(nums[i], nums[nums[i] - 1]);

交换以后，数字 x 就回到了它应该在的位置。

继续处理当前位置 i，因为交换过来的新数字也可能是一个还没归位的合法数字。

所以这里要使用 while，不是 if。

为什么需要这个判断

代码中的循环条件是：

while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])

前两个条件：

nums[i] >= 1 && nums[i] <= n

表示当前数字必须在 1 ~ n 范围内。

如果数字小于等于 0，或者大于 n，它不会影响答案，不需要移动。

最后一个条件：

nums[nums[i] - 1] != nums[i]

是为了避免重复元素导致死循环。

例如：

nums = [1,1]

当处理第二个 1 时，它应该去的位置是下标 0。

但下标 0 已经是 1 了。

如果继续交换，就会在两个相同的 1 之间反复交换，没有任何意义。

所以只有当目标位置不是当前数字时，才需要交换。

公式推导

一个合法数字 x 的正确下标是：

x - 1

这个关系来自数组下标从 0 开始，而正整数从 1 开始。

如果所有数字都归位，那么应当有：

nums[0] = 1

nums[1] = 2

nums[2] = 3

也就是：

nums[i] = i + 1

所以第一处不满足这个等式的位置 i，对应的缺失正数就是：

i + 1

如果所有位置都满足：

nums[i] = i + 1

说明 1 ~ n 全部出现了。

此时答案就是：

n + 1

正确性证明

我们证明算法返回的数就是数组中没有出现的最小正整数。

结论 1：所有能归位的合法数字都会被放到正确位置

对于任意数字 x，如果：

1 <= x <= n

那么它的正确位置是下标：

x - 1

当算法在某个位置遇到 x，并且 nums[x - 1] != x 时，就会把 x 交换到下标 x - 1。

如果 nums[x - 1] == x，说明 x 已经在正确位置，或者已经有一个相同的 x 占据了正确位置。

因此，对于每个在数组中出现过的合法正数 x，最终下标 x - 1 上一定会有 x。

结论 2：如果 nums[i] != i + 1，那么 i + 1 没有出现

反设 i + 1 出现过。

因为 i + 1 在 1 ~ n 范围内，所以根据结论 1，它最终应该被放到下标：

(i + 1) - 1 = i

也就是说最终应该有：

nums[i] == i + 1

这和 nums[i] != i + 1 矛盾。

所以如果扫描到某个位置 i 不满足 nums[i] == i + 1，就说明 i + 1 没有出现。

结论 3：第一个不匹配的位置就是最小缺失正数

算法从左到右扫描数组。

如果前面所有位置 0 ... i - 1 都满足：

nums[j] == j + 1

说明：

1, 2, ..., i

都出现过。

而当前位置 i 不满足：

nums[i] == i + 1

根据结论 2，i + 1 没有出现。

所以 i + 1 就是没有出现的最小正整数。

如果所有位置都匹配，说明 1 ~ n 都出现过，答案就是 n + 1。

因此算法正确。

举例理解

以：

nums = [3,4,-1,1]

为例。

数组长度 n = 4，只关心 1 ~ 4。

开始处理下标 0：

  • nums[0] = 3
  • 3 应该去下标 2
  • 交换后数组变成 [-1,4,3,1]

继续处理下标 0：

  • nums[0] = -1
  • 不在 1 ~ 4 范围内，不处理

处理下标 1：

  • nums[1] = 4
  • 4 应该去下标 3
  • 交换后数组变成 [-1,1,3,4]

继续处理下标 1：

  • nums[1] = 1
  • 1 应该去下标 0
  • 交换后数组变成 [1,-1,3,4]

最后扫描：

  • 下标 0 是 1，正确
  • 下标 1 不是 2

所以缺失的第一个正数是：

2

复杂度分析

每个数字最多被交换到自己的正确位置一次。

虽然代码中有 while，但所有交换次数总共不会超过 O(n)。

因此时间复杂度是：

O(n)

算法只在原数组上交换元素，除了几个变量外没有使用额外存储。

所以空间复杂度是：

O(1)