【笔记】数据结构

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);//赋初值为0
for(i=0;i<n;i++){
if(A[i]>0&&A[i]<=n)
//若A[i的值介于1~n，则标记数组B
B[A[i]-1]=1;
for(i=0;i<n;i++)
//扫描计数数组，找到目标值K
if(B[i]==0)break;
return i+1;//返回结果；
}

}

(3)以上算法的时空复杂度都是O(n)

原文地址：https://blog.csdn.net/m0_52024881/article/details/142732756

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！