欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

数组 a[N],包含 1 到 N-1 个数字,其中某个数字重复了一次。求重复的数字。时间复杂度必须为 o(N)

最编程 2024-05-27 09:48:42
...
【深圳】源创会:5.26下午、轰趴馆等你”
一个很简单的思路, 首先初始化一个n-1大小的0数组,比如我们的原始数组为a[n]={4,2,1,2,3}(n=5),那么0数组就是[0,0,0,0]。 循环从0下标开始: 那么第一次a[0]=4,置b[a[0]-1]即b[3]=1,现在0数组为[0,0,0,1]。 第二次a[1]=2,置b[a[1]-1]即b[1]=1,现在0数组为[0,1,0,1]。 第三次a[2]=1,置b[a[2]-1]即b[0]=1,现在0数组为[1,1,0,1]。 第四次a[3]=2,而0数组中b[a[3]-1]即b[1]=1,表示2存在,直接return,完成寻找 这样做的好处就是,运气好的话连一遍数组都不用遍历就找到了元素。 需要注意的几点: 1.数组b的初始化,使用memset,当然也可以有其他方法,不过这样更方便了。 2.函数是在1到n-1的限制下的,放到其他地方并不适用。 int do_dup(int a[],int n){ int b[n-1]; //数组初始化 memset(b,0,sizeof(int)*(n-1)); int i; for(i=0;i

推荐阅读