力扣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 < nums.length; i++){
            if(nums[i] <= 0)
                nums[i] = nums.length+1;
            // System.out.print("//"+nums[i]);
        }

        for(int i = 0; i < nums.length; i++){
            // System.out.print("//"+nums[i]);
            //这里加绝对值是因为可能这个数还没用过，结果因为前面的数的下标映射过来变为负值
            int x = Math.abs(nums[i]);
            if(x <= nums.length)
                //加绝对值是因为可能出现重复数变回正值
                nums[x-1] = -Math.abs(nums[x-1]);
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0)
                return i+1;
        }
        return nums.length+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24