给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

哈希表-数组自身作为哈希表，

数组原值是键，键减1是值。为了保存值，我们需要找到数组中索引为值的元素，给它加个负号。 但是数组中可能有负数，为了避免混乱，我们先把负数改为区间外的数，例如N+1。注意数组中可能有重复元素， 所以为了保证操作的幂等性，我们需要在操作时给数组元素的绝对值加负号。注意到我们遍历到的数可能是被操作过的数， 因此可能有负号，而我们已确保数组元素的原值都是正数，所以对新元素，我们需要用绝对值来获取原值，然后计算索引。

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

为什么获取num时必须取绝对值？因为第一个值对应的索引可能在后面，这样当我们遍历到这个索引处时，它是负数，必须取绝对值才能获得原值。符号代表该索引对应的元素（元素值为索引+1）已出现。我们必须根据原值来计算索引。

为什么取反时必须取绝对值？因为数组中可能存在重复元素，重复元素对应的索引是一样的，所以遍历到第一个重复元素时会把对应的索引处的元素取反，第二次取反时如果不加绝对值，那么负数又变成正数了，加上绝对值会一直是负数，这样最后检查的时候就能检查出来。

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

例子：3,2,-1,1，3,2,1,1.

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 第一步：将所有小于等于 0 的数替换为 n + 1
        // 因为我们关心的是 1 到 n 之间的正整数，任何小于等于 0 的数或大于 n 的数都可以忽略
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        // 第二步：使用数组下标作为哈希表来标记存在的数字
        // 遍历数组，将数组中值在 1 到 n 之间的元素对应的下标位置的值设为负数
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                // 将对应下标位置的值设为负数，表示 num 存在。
                // 以3,2,1,1为例，遇到第一个1时把索引0处的3变成-3，遇到第二个1时还要把第一个数取反，如果不加绝对值，则-3又变成3了，
                // 这样第三步就会误以为1没出现。
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 第三步：再次遍历数组，找到第一个正数的位置
        // 这个位置对应的下标加 1 就是缺失的第一个正整数
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // 如果所有位置上的数都为负数，说明数组包含了 1 到 n 的所有正整数
        // 因此返回 n + 1
        return n + 1;
    }
}

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

置换

如果数组中包含 x 属于 [1, N] ，那么恢复后，数组的第 x-1 个元素为 x 。第一遍遍历：将每个数放到其正确的位置上。第二遍遍历：查找第一个没有在正确位置上的数

除了打标记以外，我们还可以使用置换的方法，将给定的数组「恢复」成下面的形式：

如果数组中包含 $x \in[1, N]$ ，那么恢复后，数组的第 $x-1$ 个元素为 $x$ 。

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

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

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

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

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 第一遍遍历：将每个数放到其正确的位置上
        for (int i = 0; i < n; ++i) {
            // 当 nums[i] 是一个正数，并且在 [1, n] 范围内，且它不在正确的位置上
            // 确保[1,n]中的每个元素对应的位置处的元素都是正确的，例如第一个位置应该是1，……，第n个位置应该是n。
            // 把这些位置确定好后，剩下的不正确的位置代表的就是缺失的元素。对每个位置，while循环会一直操作，
            // 使得当前位置的数字只要是指定范围内的正数，就一定位于正确的位置。即while循环不一定只让一个数字位于正确的位置。
            // 注意不是nums[i] != i+1（这个是检查当前位置的数是不是指定数，有可能永远也不成立，因为这个指定数缺少了），应该检查当前数是不是在指定位置。
            // 检查当前位置的数对应的位置处的数是否正确，如果否，则交换，交换后当前位置的元素已改变，应该继续检查，除非换过来一个越界的数。
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 将 nums[i] 放到正确的位置——nums[i] - 1 上
                int temp = nums[nums[i] - 1]; // 临时变量保存目标位置上的数
                nums[nums[i] - 1] = nums[i];  // 将当前数放到目标位置上
                nums[i] = temp;               // 将目标位置上的数放回当前位置
            }
        }

        // 第二遍遍历：检查每个位置的数是不是正确，找第一个有问题的位置。
        for (int i = 0; i < n; ++i) {
            // 如果 nums[i] 不等于 i + 1，说明 i + 1 这个正整数缺失
            if (nums[i] != i + 1) {
                return i + 1; // 返回第一个缺失的正整数
            }
        }

        // 如果所有位置上的数都在正确的位置上，说明缺失的是 n + 1
        return n + 1;
    }
}

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