题解 | #缺失的第一个正整数#哈希+数学策略

    /*public int minNumberDisappeared (int[] nums) {
        HashSet<Integer> isFind = new HashSet<>();
        //当前没出现最小的是1，碰到1就往上看看2出现过没有
        int curMinPositive = 1;
        for(int num:nums){
            isFind.add(num);
            if(num==curMinPositive){
                //循环查看下一个没出现过的是谁
                while(isFind.contains(curMinPositive)){
                    curMinPositive++;
                }
            }
        }
        return curMinPositive;
        
    }*/
    //nums的长度为n，在最整齐的情况下nums里的元素应该是[1....n]，那么缺失的第一个正整数就是n+1
    //如果不是这样，那么缺失的第一个正整数肯定是在[1...n]之中，如何找到这个缺的呢？
    //将nums中属于[1...n]的数对应的下标，比如说2，就在序号为2，也就是下标为1的地方做一个标记
    //如果nums中所有位置都有标记，那么结果就是n+1，否则第一个没有标记的序号就是缺失的正整数
    //标记怎么做？设计为什么？设计成那个数的相反数最好了，这样不管是那个下标是否处理过，只要是我们都面对
    //绝对值来操作就不会有问题，而若是设计成别的数，比如-1就会顶掉那个下标的数，就会复杂化了。
    public int minNumberDisappeared (int[] nums) {
        if(nums==null||nums.length==0) return 1;
        int N = nums.length;
        //1.负数和0变成n+1
        for(int i = 0;i<N;i++){
            if(nums[i]<=0){
                nums[i] = N+1;
            }
        }
        //2.绝对值<=N的对应下标变成相反数
        for(int i = 0;i<N;i++){
            int cur = Math.abs(nums[i]);
            if(cur<=N){
                nums[cur-1] = nums[cur-1]<0?nums[cur-1]:-nums[cur-1];
            }
        }
        //3.遍历找到第一个非负的序号，那就是缺的
        for(int i = 0;i<N;i++){
            if(nums[i]>=0){
                return i+1;
            }
        }
        return N+1;
    }