题解 | #缺失的第一个正整数,时间O(n),空间O(1)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */     
    public int minNumberDisappeared (int[] nums) {
        if (nums == null || nums.length == 1) return 1 ;
        //缺失的最小数一定在[1-len]
        int len = nums.length ;
        //对于nums[i]，若其在[1-len]之间，则将其放入正确位置，即i-1处；若不在[1-len]则不管，i++
        for(int i = 0 ; i < len ; i ++) {
            //若nums[i]在[1-len]之间，则将其放入正确位置（交换），交换后，
            //新的nums[i]再继续此操作，直到nums[i]不在[1-len]或者
            //nums[i]和其即将交换的位置的元素nums[nums[i]-1]相等
            while(nums[i] >= 1 && nums[i] <= len && nums[i] != i+1 && nums[i] != nums[nums[i]-1]) {
                swap(nums, i , nums[i]-1) ;
            }
        }
        //遍历，如果位置i的元素不是i+1，说明此位置缺失i+1
        for(int i = 0 ; i < len ; i ++) {
            if(nums[i] != i+1) return i + 1 ;
        }
        //如果都在正确的位置，（即[1-len]都出现了），那么直接返回len+1
        return len + 1 ;
    }
    public void swap(int[] arr , int i , int j) {
        int t = arr[i] ;
        arr[i] = arr[j] ;
        arr[j] = t ;
    }
}