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

 

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

解析

我们利用变换正负属性的技巧，把<=0的数都变成一个大数，因为缺少的第一个正整数最大就是n+1（排满了就是 1 2 3 4 5），这样我们根据val值去更新val-1 下标对应的位置，将其变为负数。然后再去遍历我们就会得出大于0的都是不存在的。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //将负数转化为一个特别大的数
        for(int i = 0 ;i < n ; i ++){
            if(nums[i]<=0){
                nums[i] = 2*n;
            }
        }
        //判断符合范围要求的数值
        for(int i = 0 ; i < n ; i ++){
            int val = Math.abs(nums[i]);
            if(val<=n){
                nums[val-1] = -1 * Math.abs(nums[val-1]);
            }
        }
        for(int i = 0 ;i < n ; i++){
            if(nums[i]>0){
                return i+1;
            }
        }
        return n+1;
    }
}

注意：本文归作者所有，未经作者允许，不得转载