免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2743 | 回复: 9

找两个相同的数字(高手进来呀) [复制链接]

论坛徽章:
0
发表于 2010-04-09 15:21 |显示全部楼层
最近碰到个题目,说给你一个数组。里面有很多数字,假设里面肯定只有两个数字是重复,怎么找出那两个数? 时间复杂度控制在O(n)之内。

论坛徽章:
0
发表于 2010-04-09 15:40 |显示全部楼层
先设置一个合理的哈西值并申明一个哈西值大小的数组,然后依次对每个数以这个哈西值取模,再判断数组中这个模的位置有没有被置位,如果置了,则找到,未置则置位.

论坛徽章:
0
发表于 2010-04-09 15:58 |显示全部楼层
嗯,这个方法好像还不错,但是那个合理的哈希值有点难呃。。。。。
比如如果是100000个数字。   让我也想会先。

论坛徽章:
0
发表于 2010-04-09 16:21 |显示全部楼层
如果你要分析的数组里最大值不超过你物理内存的话,也无所谓哈西不哈西了,直接malloc一块最大成员大小的区域,查的时候把数组成员的值作为地址.

论坛徽章:
1
天秤座
日期:2014-04-27 07:42:20
发表于 2010-04-09 17:00 |显示全部楼层
楼上,找最大成员就远超O(n)了。

论坛徽章:
0
发表于 2010-04-09 17:13 |显示全部楼层
楼上,找最大成员就远超O(n)了。
A.com 发表于 2010-04-09 17:00



    最大成员要找吗?long型就是2^32, short型就是2^16,数组的类型已经决定了.

论坛徽章:
1
天秤座
日期:2014-04-27 07:42:20
发表于 2010-04-09 17:16 |显示全部楼层
{:3_196:}万一人家说的数组是一组数字的意思呢?

论坛徽章:
0
发表于 2010-04-09 17:28 |显示全部楼层
万一人家说的数组是一组数字的意思呢?
A.com 发表于 2010-04-09 17:16



    你这样的假设没有任何意义,怎么不假设数组都是128位的整型?

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:50:28
发表于 2010-04-09 17:57 |显示全部楼层
构建一个map,把数字一个一个的放入map里,直到找到有重复的。
因为是数字,所以根本不用进行hash。

论坛徽章:
0
发表于 2010-04-09 18:28 |显示全部楼层
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP