2018 408应用题41
给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或者C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
解决办法
（1）算法思想：设要查找的数组中未出现的最小正整数为K。K的取值范围只能是【1，n+1】。采用类似计数排序的思想，分配一个数组B[n]，用来标记A中是否出现了1~n之间的正整数。从左至右依次扫描数组元素A[i]并标记数组B。若A[i]是负数、零或是大于n，则忽略该值；否则，根据计数排序的思想将B[A[i] - 1]置为1。标记完毕，遍历数组B，查找第一个值为0的元素，其下标+1即为目标元素K；找不到0时，K = n + 1。
(2)算法实现
int findMissMin(int A[],int n){int i,*B;//标记数组B=(int*)malloc(sizeof(int)*n);//分配空间memset(B,0,sizeof(int)*n);//赋初值为0for(i=0;i<n;i++){if(A[i]>0&&A[i]<=n)//若A[i的值介于1~n，则标记数组BB[A[i]-1]=1;for(i=0;i<n;i++)//扫描计数数组，找到目标值Kif(B[i]==0)break;return i+1;//返回结果；}}
(3)以上算法的时空复杂度都是O(n)