41.缺失的第一个正数 困难

问题：

给你一个未排序的整数数组 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 到 n + 1 之间（n为数组长度）

比如1234，最小正整数是5，3457，最小正整数是1

不能引用哈希表等空间，所以遍历数组，把每个数字 i 放在 i - 1 的位置上

再次遍历交换完位置的数组，如果当前位置 i + 1的结果和数字不匹配，则 i + 1就是缺失的最小正整数

var firstMissingPositive = function(nums) {
    let n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            let index = nums[i] - 1;
            [nums[i], nums[index]] = [nums[index], nums[i]]
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
};