LeetCode17 - 缺失的第一个正数

📝 题目描述

给你一个未排序的整数数组 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

💡 解题思路

方法一：标记法

如果题目没有空间复杂度要求，那么很容易想到的一个解法就是将数组所有的数放入哈希表（set），随后从 1 开始依次枚举正整数，并判断其是否在哈希表中，这种做法的时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

上面做法中，耗费空间的地方就在于开了一个哈希表，因此从这点入手，我们可以考虑将输入数组设计成哈希表的替代品。

实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 $[1,N+1]$ 中。这是因为如果 $[1,N]$ 都出现了，那么答案是 $N+1$ ，否则答案是 $[1,N]$ 中没有出现的最小正整数。

我们对数组进行遍历，对于遍历到的数 x，如果它在 $[1,N]$ 的范围内，那么就将数组中的第 x−1 个位置（因为数组下标从 0 开始）打上“标记”。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。

接下来我们思考如何设计“标记”：由于我们只在意 $[1,N]$ 中的数，因此我们可以先对数组进行遍历，把不在 $[1,N]$ 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将“标记”表示为「负号」。

具体流程如下：

将数组中所有小于等于 0 的数修改为 $N+1$ ；
遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 $∣x∣$ ，其中 $∣∣$ 为绝对值符号。如果 $∣x∣∈[1,N]$ ，那么我们给数组中的第 $∣x∣−1$ 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 $N+1$ ，否则答案是第一个正数的位置加 1。

方法二：置换法

除了添加标记，我们也可以把处于区间 $[1,N]$ 中的数（x）交换到合适的位置（下标为x-1处）。

在恢复后，数组应当有 $[1, 2, ..., N]$ 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 $[3, 4, -1, 1]$ 为例，恢复后的数组应当为 $[1, -1, 3, 4]$ ，我们就可以知道缺失的数为 2。

那么我们如何将数组进行恢复呢？我们可以对数组进行一次遍历，对于遍历到的数 $x=nums[i]$ ，如果 $x∈[1,N]$ ，我们就知道 $x$ 应当出现在数组中的 $x−1$ 的位置，因此交换 $nums[i]$ 和 $nums[x−1]$ ，这样 $x$ 就出现在了正确的位置。在完成交换后，新的 $nums[i]$ 可能还在 $[1,N]$ 的范围内，我们需要继续进行交换操作，直到 $x \notin [1,N]$ 。

注意到上面的方法可能会陷入死循环。如果 $nums[i]$ 恰好与 $nums[x−1]$ 相等，那么就会无限交换下去。此时我们有 $nums[i]=x=nums[x−1]$ ，说明 $x$ 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。

由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 $N$ ，整个方法的时间复杂度为 $O(N)$ 。

🔧 代码实现

1、标记法

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

        // 修改非正整数为n+1
        for (int& num: nums) {
            if (num <= 0) {
                num = n + 1;
            }
        }

        // 标记已有的合法正整数的位置为负数
        for(int i = 0; i < n; i++){
            if(abs(nums[i]) > 0 && abs(nums[i]) <= n){
                nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
            }
        }

        // 返回答案
        for(int i = 0; i < n; i++){
            if(nums[i] > 0){
                return i + 1;
            }
        }

        return n + 1;
    }
};

2、置换法

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        // 开始交换
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                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;
    }
};

📊 复杂度分析

1、标记法

时间复杂度： $O(N)$ ，其中 $N$ 是数组的长度。
空间复杂度： $O(1)$ 。

2、置换法

时间复杂度： $O(N)$ ，其中 $N$ 是数组的长度。
空间复杂度： $O(1)$ 。

🎯 总结

核心思想：想到最大范围是 $[1, N]$ 和用负号作为标记。