41. 缺失的第一个正数

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

示例 1:

输入: [1,2,0]
输出: 3
示例 2:

输入: [3,4,-1,1]
输出: 2
示例 3:

输入: [7,8,9,11,12]
输出: 1

解题思路

要知道的是，最小正整数，肯定是在[1,size]的范围内，size表示的是数组长度。将数组中值小于等于0的值设为size+1,size是数组的长度，表示不计入下面的操作中。然后利用数组的下标，进行标记，没出先的数组值x，将对应|x|-1的下标对应的元素值设为负数，表示该值已经出现过

举例来说， [3,2,4,-1,0]
小于等于0设为size+1 [3,2,4,6, 6]
进行标记，第一个数是3，将3-1 ，2下标标记为负数，即[3,2,-4,6,6], 意思是在所有可能出现的元素中，3已经出现了，我们将数组利用起来，作为标志，也就是下标2标记为符号，说明3已经出现，其他以此类推。
最后第一个正数就是我们的值

代码

java

class Solution {
    public int firstMissingPositive(int[] nums) {
        int size = nums.length;
        for(int i=0;i<nums.length;i++){
            if(nums[i]<=0){
                nums[i] = size+1;
            }
        }
        for(int i=0;i<nums.length;i++){
            int idx = Math.abs(nums[i]);
            if(idx<size+1){
                nums[idx-1] = -Math.abs(nums[idx-1]);
            }
        }
        for(int i =0;i<size;i++){
            if(nums[i]>0){
                return i+1;
        }
    }
    return size+1;
}
}