给定一个含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;i
给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。最先出现在Python成神之路。
共有 0 条评论