从零学算法41

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

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

示例 1：

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

输出：3

示例 2：

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

输出：2

示例 3：

输入：nums = [7,8,9,11,12]

输出：1

• 我的想法很简单，当该数组排序并去重后，再去掉小于等于 0 的部分，最终遍历数组时，判断是否为从 1 开始连续的数，比如 [1,2,3] 那就返回最大值 + 1 即 4，若不为从 1 开始的连续的数组，比如 [1,3,4] 中，nums[0] == 1，但是 nums[1] != 2，说明缺失了 2，那就直接返回 2 即可。

•   public int firstMissingPositive(int[] nums) {
    	// 排序
        Arrays.sort(nums);
        int i = 0;
        // 从大于 0 处开始遍历，相当于去除了小于等于 0 的部分
        while(i
        	// 相当于去重
            while(i
        int n = nums.length;
        for(int i = 0;i
        	// 首先数在理想数组范围
        	//  其次如果 nums[i] 上面的数如果不是 i+1 就把它换到正确的位置，继续判断换过来的数
        	// 直到 num[i] = i + 1 就结束这一轮循环
            while((nums[i]0 && nums[i] 
                swap(nums,i,nums[i]-1);
            }
        }
        for(int i = 0;i
            if(nums[i]!=i+1)return i+1;
        }
        return n+1;
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }