【数组中未出现的最小正整数】符合要求，示例没问题

整体思路

• 改造原数组，将值为的元素放到下标为的位置

• 以下2种情况将元素置0：

  1. 元素值超出范围

  2. 元素值重复

• 遍历改造后的数组， 第一个值为0的位置就是未出现的最小正整数

• 例如数组，改造后为，遍历后第一个0下标为，所以缺失的是

复杂度

• 遍历2次，时间复杂度

• 交换法，原地操作， 空间复杂度

import java.util.*;
public class Solution {
    /**
     * return the min number
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int minNumberdisappered (int[] arr) {
        int len = arr.length;
        // 预处理
        for (int i = 0; i < len; i ++) {
            // 元素小于0或大于len时，置0
            if (arr[i] <0 || arr[i] > len)
                arr[i] = 0;
            while (arr[i] > 0 && arr[i] <= len && arr[i]!=i+1) {
                // 如果arr[i]与下表为arr[i] - 1的元素相等，代表它重复了，保留1个，将其置0
                if (arr[i] == arr[arr[i] - 1]) {
                    arr[i] = 0;
                    break;
                }
                // 将元素arr[i]交换到下标为arr[i]-1的位置
                swap(arr, i, arr[i] - 1);
            }
        }
        // 遍历查找，元素为0时代表i+1缺失
        for (int i = 0; i < len; i ++) {
            if (arr[i] == 0)
                return i + 1;
        }
        return len + 1;
    }

    private void swap (int[] arr, int a, int b) {
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}