题解 | #数组中未出现的最小正整数#（附带图解）

思路:

从题中给出的有效信息：

• 无序数组 找出未出现的最小正整数
• 时间复杂度为O(n)，空间复杂度为O(1)

故此 不能申请额外空间，且由于时间为O(n),而不能直接使用排序算法（最低也是nlog(n)复杂度）加二分解决，只能进行原地算法

方法一：原地算法

具体做法：
遍历数组，将 大于0小于arr长度+1的数据n 与 原数组中下标为 n-1 的数据 进行交换，然后遍历数组将 当前数据n 和 下标为n-1 的值 不相等的一个数据 返回，若全都符合情况，则返回数组长度加1；
具体思路如以下图解：

import java.util.*;
public class Solution {
    /**
     * return the min number
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int minNumberdisappered (int[] arr) {
        // write code here
        int LEN = arr.length;
        for(int i=0; i<LEN; i++){
            //大于0小于arr长度+1的数据n 与 原数组中下标为 n-1 的数据 进行交换
            while(arr[i] <= LEN && arr[i] >= 1 && arr[i] != i+1 ){
                if(arr[i] == arr[arr[i]-1]){
                    break;
                }
                swap(arr,i,arr[i]-1);
            }
        }

        //将 当前数据n 和 下标为n-1 的值 不相等的一个数据
        for(int i=0; i<LEN; i++){
            if(arr[i] != i+1){
                return i+1;
            }
        }

        return LEN+1;
    }
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

复杂度分析：

• 时间复杂度：O(n)，最差情况是O(2n)，常数省略
• 空间复杂度：O(1)，原有数组上进行操作，未申请额外空间

方法二：暴力搜索（不推荐）

具体做法：
通过使用set集合来进行唯一判断，然后全部遍历查找求值

import java.util.*;
public class Solution {
    /**
     * return the min number
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int minNumberdisappered (int[] arr) {
        // write code here
        HashSet<Integer> hashSet = new HashSet<>();
        int index = 1;
        for (int a : arr) {
            //加入集合
            hashSet.add(a);
        }

        //依次遍历整数，查看当前值是否包含，若没有，则查找返回
        while (hashSet.contains(index)) ++ index;
        return index;
    }
}

复杂度分析：

• 时间复杂度：O(n) 主要是第二次查询需要O(n)的时间
• 空间复杂度：O(n) 申请了额外空间，需要O(n)复杂度