41.缺失的第一个正数 #

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            // 因为数组是从[0,n]的范围，基本符合题目中要求的最小正整数，从1开始
            // 我们可以将符合这个区间的元素放到正确的位置，比如nums[3] = 6 那么应该和nums[5]进行交换
            while(nums[i] > 0 && nums[i] < n && nums[nums[i] - 1] != nums[i]){
                int tmp = nums[nums[i] -1];
                nums[nums[i] -1] = nums[i];
                nums[i] = tmp;
                // 交换后这个值也满足条件，继续交换
                // 不满足条件,要不就是>n,要不就是<0,要不就是两者相等，都可以跳过
            }
        }
        for(int i = 0; i < n; i++){
            // 只要不满足nums[i] == i + 1,要不就是>n,要不就是<0,要不就是两者相等,直接返回结果
            if(nums[i] != i + 1)
                return i + 1;
        }
        // 说明1到n都存在,最小就是n+1
        return n + 1;
    }
}