[NC]30. 缺失的第一个正整数

🚩传送门：牛客题目

题目

给你一个未排序的整数数组 ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0] 输出：3

示例 2：

输入：nums = [3,4,-1,1] 输出：2

示例 3：

输入：nums = [7,8,9,11,12] 输出：1

解题思路：数组替代哈希表

下面做法显然可行，但是空间复杂度过大 。

我们可以将数组所有的数放入哈希表，随后从 1 开始依次枚举正整数，并判断其是否在哈希表中。

为了使空间复杂度较小，我们在原数组基础上操作，我们对数组进行遍历，对于遍历到的数 ，如果它在 的范围内，那么就将数组中的第 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 ，否则答案是最小的没有打上标记的位置加 **1**。

算法的流程如下：

• 我们将数组中所有小于等于 0 的数修改为 ；

• 我们遍历数组中的每一个数，如果，那么我们给数组中的第 个位置的数添加一个负号。

  注意如果它已经有负号，不需要重复添加，因为它可能已经被打上了标记

• 在遍历完成后，如果数组中的每一个数都是负数，那么答案是，否则答案是第一个正数的位置加 **1** 。

复杂度分析

时间复杂度：，其中 指的是数组长度。

空间复杂度：

官方代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //1. 负数变不在范围内的整数
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        //2. 根据数字标记相应位置
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        //3. 检查缺失数字
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        //4. 未检查到就是缺失的 N+1
        return n + 1;
    }
}

🚩解题思路：置换

除了打标记以外，我们还可以使用置换的方法。在恢复后，数组应当有 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个 缺失的正数 。

以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2 。

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

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

每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 ，因此时间复杂度为 。

复杂度分析

时间复杂度：，其中 指的是数组长度。

空间复杂度：

官方代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //1. 不停的交换
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        //2. 检查交换后不符合位置相等的
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
           //3. 说明是n+1
        return n + 1;
    }
}