免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 6940 | 回复: 20

[算法] 从一百个数中找不存在的数 [复制链接]

论坛徽章:
0
发表于 2012-11-22 15:47 |显示全部楼层
碰到个面试题目,有一百个1到100的数字,为乱序的,其中缺一个数字,简述用什么方法能够最快速的查找出缺的那个数字,以及循环多少次?大家有什么好的解法?

论坛徽章:
324
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2012-11-22 16:39 |显示全部楼层
缺一个那就是99个了,5050-累加值即可

论坛徽章:
0
发表于 2012-11-22 16:42 |显示全部楼层
楼主的意思是有一个重复的

回复 2# hellioncu


   

论坛徽章:
0
发表于 2012-11-22 16:55 |显示全部楼层
建个索引数组——1-100,初始为{0}

录入:有索引数组对应位置就+1

再轮一遍索引数组,哪个为0就缺哪个

2N{:3_189:}

论坛徽章:
0
发表于 2012-11-22 17:04 |显示全部楼层
这个题目应该出现过了,使用异或运算应该是最快的方法了,加法也可以,但是加法应该比不上逻辑运算的速度。。
(另外我也想求求关于现代CPU执行 加法的需要多少时钟周期, 逻辑异或需要多少时钟周期 ? 的干货 )

首先得到 1-100 这些数字异或后得到的数字 Y= 1^2^..^100,使用循环99次得到.
然后用着Y 去异或那个99个数的数字, 最后Y里保存的就是缺失了的数字。 也是99次循环。

其实是同学提到的,他搞ACM,我很菜。。
原理:
Y = a^b^c;

e = Y ^ a ^ c = a^b^c^a^c = a^a^b^c^c = 0 ^ b ^ 0 = b .. 就是缺少了的b,异或运算的性质应该没记错。
有错请指出下,谢谢

论坛徽章:
0
发表于 2012-11-22 17:08 |显示全部楼层
回复 5# InMySin

察,看错题目了, 100个 1-100的数字,其中缺少一个1-100中的数,那肯定有重复了。。这种解法就应该不正确了.

   

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2012-11-22 17:56 |显示全部楼层
不计代价,最快

  1. int arr[100];  //< input


  2. int *pIn=arr-1;
  3. int sig100=0;
  4. int sigdes=0;
  5. int flag[101]={0};
  6. for(int i=1;i<=100;i++){
  7.    sig100|=i;
  8.    if(flag[pIn[i]]==0){
  9.       flag[pIn[i]]=1;
  10.       sigdes|=pIn[i];
  11.    }
  12. }
  13. return sigdes|sig100;
复制代码

论坛徽章:
3
寅虎
日期:2013-11-27 07:53:29申猴
日期:2014-09-12 09:24:152015年迎新春徽章
日期:2015-03-04 09:48:31
发表于 2012-11-22 18:58 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
5
2015年迎新春徽章
日期:2015-03-04 09:58:1115-16赛季CBA联赛之上海
日期:2016-01-18 13:24:3015-16赛季CBA联赛之佛山
日期:2016-01-27 10:13:0515-16赛季CBA联赛之北控
日期:2016-08-04 22:33:2115-16赛季CBA联赛之山西
日期:2016-08-06 15:49:33
发表于 2012-11-23 09:53 |显示全部楼层
先用异或求重复数,
然后序列求和和5050比较,
少几就是重复数加几,
反之减

论坛徽章:
3
巳蛇
日期:2013-10-03 10:41:48申猴
日期:2014-07-29 16:12:04天蝎座
日期:2014-08-21 09:24:52
发表于 2012-11-23 10:55 |显示全部楼层
我能想到的和4楼一样...
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP