Chapter3: 更好的查找与排序算法

8. 实践：最小可用id是多少-求乱序数组中缺失的最小数字

问题

在乱序的非负数组中找到最小的可分配id(从1开始编号)，数据量1000000。

意思就是求一个非负乱序数组中缺失的最小数字，因为id不能重复

算法

解法1：先排好序O(nlgn)

基本思想

先将数组排好序，然后循环比较输出第一个缺失的数

解法2：用分区的思想

基本思想

在数组中查找元素，想到用排序，自然想到用划分

通过之前查找第k小的算法，比较第k小(即顺序第k位)是否等于k，得知数组左边是否紧密，进而判断缺失的最小数字是在数组左边还是右边

• 将数组划分为两部分，用 3.6 最快效率求出乱序数组中第k小的数 中的selectK(int* arr,int begin, int end,int k) 方法，求出输入数组 arr 的中间元素的值 arr[mid] (mid为中间元素下标) 是递增有序状态下的第几个元素(即第k小)

  这个方法输入的k是要找的第k小元素，返回的是第k小元素的值。

  这个方法会将元素分区，arr[mid] 左边的元素比它小，右边的元素比它大

  这里用这个方法来比较第k小的元素(顺序第k个元素)是否等于k以判断这个元素

  的左边是否是紧密的，详见下面解释

• 比较 arr[mid] 是否等于其下标+1，即 mid+1

  • 如果等于，则说明arr 的左边是紧密的，因为分区后在 arr 中其左边的元素都比它小，如果 arr[mid]=mid+1 (意味者第mid位元素的值=mid，比如第50个元素=50), 说明左边必然是 [1,mid] 这些元素1个萝卜1个坑(虽然不一定有序)，那查找最小缺失值就要到右边去查找
  • 如果不等于，比如说第50个元素不等于50 (不可能能小于50，因为左边有49个小于它且不重复的正整数, 只会是大于50),那因为着必然有1到50的自然数不在左边，查找最小缺失值就要在左边查找

• 递归划分找到这个最小的值

代码

用分区的思想查找乱序数组中的最小缺失数

/*寻找下一个可用的最小Id
在乱序数组中寻找最小缺失数
参数：arr 输入数组地址,begin当前划分数组的开始位置下标，end结束位置下标*/
int findNextId(int* arr,int begin,int end){
    
    if(begin>end){//出口条件 
        return begin+1;//自己列出实例观察   
    }
    int mid = begin+((end-begin)>>1);//中间元素的下标 
    int midK = mid-begin+1;//当前数组划分中中间元素的位置，即第几个(不是下标) 
    int q = selectK(arr,begin,end,midK); //中间元素的值
    if(q==mid+1)//左边是紧密的 
        return findNextId(arr,mid+1,end);//在右边查找缺失值
    else
        return findNextId(arr,begin,mid-1); //在左边查找缺失值
    
}

乱序数组中寻找第k小元素(即顺序的第k个元素)

/*乱序数组中寻找第k小元素(即顺序的第k个元素)*/
int selectK(int* arr,int begin, int end,int k){
    int q = partition2(arr,begin,end);//主元的下标 
    int nowQ=q-begin+1;//nowK:主元在当前的数组划分中是第几个元素(注意不是下标) 
    if(nowQ<k)//当前主元位置小于k,即k在主元右侧 
        return selectK(arr,q+1,end,k-nowQ);//在右数组中k新的相对位置下标(代入nowQ的值发现等价与k+begin-(q+1))//即新的k的下标    
    else if(nowQ>k)
        return selectK(arr,begin,q-1,k);//k在当前数组划分的左半部分，位置还是ke 
    else
        return arr[q];//索引元素值的时候又得用回下标q了 
}

双向扫描分区函数,将数组分为两部分左边小于主元，右边大于主元

/*双向扫描分区函数,将数组分为两部分左边小于主元，右边大于主元*/
int partition2(int arr[],int begin,int end){
    int pivot=arr[begin];
    int left=begin+1;
    int right=end;
    while(left<=right){
        while(left<=right&&arr[left]<=pivot)//因为left在变化所以这里也要有left<=right的判断条件
            left++;
        while(left<=right&&arr[right]>pivot)
            right--;
        //当arr[left]>pivot&&arr[right]<=pivot时，交换它俩的值
        if(left<right){//如果left==right就没有交换的必要了
            int tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
        }
    }
    int tmp=arr[begin];//交换主元到右指针的位置
    arr[begin]=arr[right];
    arr[right]=tmp;
    
    return right;
}

解法3：用辅助数组O(n)

基本思想

• 创建辅助数组 auxArr[arrLen]={0},注意 arrLen 为输入数组 arr 的长度，而不是输入数据的最大值
• 因为输入数组长度为arrLen ,所以最小的缺失值一定是在 [1,arrLen] 区间内
• 遍历输入数组 arr,如果出现元素值 x (1<=x<=arrLen) ，则将辅助数组 auxArr 中对应下标为 x 的元素值设为1;如果 x>arrLen 就不用统计了，反正也不可能是要找的缺失值。
• 遍历辅助数组 auxArr ,输出 auxArr 第一个值为0的元素的下标，即为题意要找到最小缺失值

第一遍遍历时间复杂度O(n), 第二遍也是O(n),根据加法原则整个算法的时间复杂度就是O(n),不过这个方法有o(n)的空间开销

代码

/*寻找下一个可用的最小Id
在乱序数组中寻找最小缺失数
参数：arr 输入数组地址,arrLen输入数组长度*/
int findNextId(int* arr,int arrLen){
    int auxLen=arrLen+1;//辅助数组长度，因为没用auxLen[0]所以要+1 
    int auxArr[auxLen]={0};
    for(int i=0;i<arrLen;i++){
        if(arr[i]<=arrLen)//最小缺失数只可能在这个范围内 
            auxArr[arr[i]]=1;//目标数组中的数作为辅助记录数组的下标 
    } 
    
    //返回最小的缺失数的下标 
    for(int i=1;i<auxLen;i++){ 
        if(auxArr[i]==0)
            return i;
    }
    //输入数组中没有缺失数，则下一个可用id是输入数组元素的最大值+1 
    return (arrLen+1);
}

解法4：暴力解法

基本思想

用双层循环挨个查找1...n是否在数组中，比如1是否在数组中，2是否在数组中...