题解 | #数组中未出现的最小正整数#

题解一:Hash+遍历(不符合题目要求)
主要思路:
根据题意n的范围是 $1 - 10^9$ ，建立hash表
①对数字散列到hash表，非正整数忽略
②对hash表进行从小到大的遍历，对应key值没有value的bucket即为第一个未出现的最小正整数

图示
图片说明

复杂度分析:
时间复杂度分析: $O(N)$ ,散列的时间为O(N),而遍历时间复杂度也为O(N),综上时间复杂度为O(N)
空间复杂度分析: $O(N)$ ，开辟了一个最大的为N的hash表

实现如下：

int hash_table[1000000000];//hash表，放在外面定义的原因是，可能超过了栈空间
class Solution {
public:
    /**
     * return the min number
     * @param arr int整型vector the array
     * @return int整型
     */
    int minNumberdisappered(vector<int>& arr) {
        // write code here
        for(auto i:arr){
            if(i<0)continue;//负数不用关心
            else hash_table[i]=i;//散列
        }
        for(int i=1;i<1000000000;i++){
            if(hash_table[i]!=i) return i;//找未出现的最小正整数
        }
        return 0;
    }
};

题解二：原地交换
主要思路:根据题目要求，时间复杂度为O(N),空间复杂度为O(1),那么只能在原地采用交换策略的算法处理本算法题
①未出现的最小正整数一定是从1开始的，我们的的数组大小为n，那么对于大于n的与小于等于0的数我们可以抛弃掉；
②将大于0与小于等于n的数字与数组下标为n-1的数据交换
③遍历数组找到下标n与数字为n+1不匹配的第一个数，找不到则代表全部缺失的是第n+1个数

图示：
图片说明

复杂度分析:
时间复杂度分析: $O(N)$ ,通过一轮遍历都能将数字交换到对应的下标处，因为while循环未来把数字与对应的下标对应上，不会对假设对整个数组遍历了，那么数字都会对应到正确的位置，后续不会跳入while循环执行
空间复杂度分析: $O(1)$ ，原地交换

实现如下:

class Solution {
public:
    /**
     * return the min number
     * @param arr int整型vector the array
     * @return int整型
     */
    int minNumberdisappered(vector<int>& arr) {
        // write code here
        if(arr.size()==0)return 0;//特判
        int n=arr.size();
        for(int i=0;i<n;++i){
            while(arr[i]!=i+1){////数字n与下标n-1不对应，需要交换；
                if(arr[i]<=0||arr[i]>n||arr[i]==arr[arr[i]-1])//arr[i]是非正整数，或者大于n，或者已经与下标正确对应
                    break;
                //交换，将arr[i]放到arr[i]-1的下标位置
                int index=arr[i]-1;
                arr[i]=arr[index];
                arr[index]=index+1;
            }
        }
        for(int i=0;i<n;++i){//找未出现的最小正整数
            if(arr[i]!=i+1)
                return i+1;
        }
        return n+1;//下标与数字都对应，返回n+1；

    }
};