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是否在数组中...
