力扣41 缺失的正数

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

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

示例 1：

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

输出：3

解释：范围 [1,2] 中的数字都在数组中。

示例 2：

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

输出：2

解释：1 在数组中，但 2 没有。

数据结构：原数组

算法：

本题是一道困难题，主要是因为要求空间复杂度为o(1),时间复杂度为o(n)。

这题最初的思路是用一个哈希表，将数组存入，然后从1开始找第一个哈希表中不存在的数就是缺失的正数。

上述做法空间复杂度明显不是常数级别，有没有什么办法使用原数组当做哈希表呢？那第一个要解决的问题就是长度，这题答案其实只能在【1，length+1】中出现，因为但凡有一个位置不是这个范围内的数，那就必定有一个这个范围内的数没出现。一个萝卜一个坑对不？

解决了第一个长度问题，那就还有如何映射的问题，也就是我怎么知道范围里的数有没有出现过。很好办，只要它出现了，我们就将它转换成下标，将对应的值转换为负值。那么最后没有变成负值的数，它对应的下标就是我们要找的范围里的数咯！

然后第二个问题还有一个小麻烦，就是事先要讲数组中的负数变为一个不可能出现的数防止干扰，同时在真正遍历的时候要加绝对值哦，看下面代码解释：

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i = 0; i