给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。

算法思想:首先要知道这个正整数的范围,因为是n个整数,最小的正整数x一定在1到n+1这个范围之间,为什么呢,假如这个数组为a[1,2,3,4,5]
此时最小正整数为6,就是n+1,如果出现1到n之间没有出现的这个x也在1—n+1这个范围
确定了范围,我们多设立一个数组b,同时多分配两个空间b[n+2],初始值全部为0,然后对a[i]进行遍历,如果0
int a[4]={-5,3,2,3};
int n=4;
int ans=0;
int FindMin(int a[],int n){
int b[n+2]={0};
for(int i=0;i0&&a[i]<=n+1) b[a[i]]=1; }

给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。最先出现在Python成神之路

版权声明:
作者:Mr李
链接:https://www.techfm.club/p/28516.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>