免费注册 查看新帖 |

Chinaunix

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

有100万个数字(1到9),其中只有1个数字重复2次,如何快速找出该数字 [复制链接]

论坛徽章:
0
发表于 2011-08-04 09:02 |显示全部楼层
在CSDN上看到的,有点意思,有啥好办法?

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2011-08-04 09:14 |显示全部楼层
1到9?100万?那么每个数字至少得出现10万次吧??

论坛徽章:
0
发表于 2011-08-04 09:17 |显示全部楼层
遍历一遍, 关健是遍历过程中, 每新发現一个肯定不是解,就时刻注意当前还可能为解的数目.
极端情形下,没啥好办法.

比如
前999998 为某个整数, 最后2个为某个整数.

看上去这题目没啥意思,o(n)不可避免

论坛徽章:
0
发表于 2011-08-04 09:24 |显示全部楼层
回复 3# peidright


    问题是这个“新”字

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2011-08-04 09:51 |显示全部楼层
遍历一遍, 关健是遍历过程中, 每新发現一个肯定不是解,就时刻注意当前还可能为解的数目.
极端情形下,没啥好 ...
peidright 发表于 2011-08-04 09:17



    你在O(1)的空间下,能做到O(n)的复杂度??在没有特殊的算法的前提下(如异或)可能么?

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2011-08-04 10:01 |显示全部楼层
回复 1# qishking


    没有实用价值,编造的题目, 是shit.

论坛徽章:
0
发表于 2011-08-04 11:02 |显示全部楼层
回复 5# starwing83


    , 这里我的O(n)的意思是1000000, 不是 10., 搞个uint8 a[10]; 直接数就行了.
    一点点的工程義義就是, 当以经发现9个大与2的情况, 就直接可以得到必然另外那个数是xx
    应该是道没任何義义的题目

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2011-08-04 11:10 |显示全部楼层
回复 7# peidright


    如果只有1~9九个数字,肯定没意义,我回过了,但是假设有999999个各不相同的32位数,有一个数字和前面的一个数字重复,请问如何找到这个重复的数字呢?

论坛徽章:
0
发表于 2011-08-04 11:46 |显示全部楼层
回复 8# starwing83


    没办法.!

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2011-08-04 12:23 |显示全部楼层
回复 9# peidright


    是这样的,我以前好像看过类似的题目,有一个很巧妙的异或的解法。我去matrix67的博客找找……
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP