017.缺失的第一个正数

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 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

题目思路

由于题目要求我们**「只能使用常数级别的空间」**，而要找的数一定在[1, N + 1]左闭右闭（这里N是数组的长度）这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组；

我们要找的数就在[1, N + 1]里，最后N + 1这个元素我们不用找。因为在前面的N个元素都找不到的情况下，我们才返回N + 1；

那么，我们可以采取这样的思路：就把1这个数放到下标为0的位置，2这个数放到下标为1的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第1个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。

这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为i的数映射到下标为i - 1的位置。

图解

题解代码

/**
 *  时间复杂度高
 * @param nums
 * @return
 */
public int firstMissingPositive(int[] nums) {
    int[] array = Arrays.stream(nums).distinct().filter(x -> x > 0).sorted().toArray();
    for (int i = 0; i < array.length; i++) {
        if (array[i] - 1 != i) {
            return i + 1;
        }
    }
    return array.length + 1;
}

// 和上面的思想一样，希望将 1放到0索引处，2放到1索引处，依次类推
// 使用了这原数组上交换元素的方法，时间复杂度和空间复杂度都低
/**
 *  时间复杂度，空间复杂度都低
 * @param nums
 * @return
 */
public int firstMissingPositive2(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 如果遍历到3，我就希望把他放到索引2处，即swap(nums, i, nums[i] - 1);
        // 这里i索引处的值nums[i]=3,交换他和 nums[i]-1「2」处的值，3就到了2索引处
        // 前提是 nums[nums[i] - 1] != nums[i]
        while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    // 如果不是0索引处为1，则缺的就是1，依次类推
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] - 1 != i) {
            return i + 1;
        }
    }
    return nums.length + 1;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}