免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 找两个相同的数字（高手进来呀）
最近访问板块 发新帖
查看: 2780 | 回复: 9
打印 上一主题 下一主题

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

wohenry84

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2010-04-09 15:21 |只看该作者 |倒序浏览
最近碰到个题目，说给你一个数组。里面有很多数字，假设里面肯定只有两个数字是重复，怎么找出那两个数？ 时间复杂度控制在O（n）之内。
samlumengjun

论坛徽章:
0
2楼 [报告]
发表于 2010-04-09 15:40 |只看该作者
先设置一个合理的哈西值并申明一个哈西值大小的数组,然后依次对每个数以这个哈西值取模,再判断数组中这个模的位置有没有被置位,如果置了,则找到,未置则置位.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
wohenry84

论坛徽章:
0
3楼 [报告]
发表于 2010-04-09 15:58 |只看该作者
嗯，这个方法好像还不错，但是那个合理的哈希值有点难呃。。。。。
比如如果是100000个数字。   让我也想会先。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
samlumengjun

论坛徽章:
0
4楼 [报告]
发表于 2010-04-09 16:21 |只看该作者
如果你要分析的数组里最大值不超过你物理内存的话,也无所谓哈西不哈西了,直接malloc一块最大成员大小的区域,查的时候把数组成员的值作为地址.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
A.com

论坛徽章:
1
天秤座 日期:2014-04-27 07:42:20
5楼 [报告]
发表于 2010-04-09 17:00 |只看该作者
楼上，找最大成员就远超O（n）了。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
samlumengjun

论坛徽章:
0
6楼 [报告]
发表于 2010-04-09 17:13 |只看该作者
楼上，找最大成员就远超O（n）了。
A.com 发表于 2010-04-09 17:00



    最大成员要找吗?long型就是2^32, short型就是2^16,数组的类型已经决定了.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
A.com

论坛徽章:
1
天秤座 日期:2014-04-27 07:42:20
7楼 [报告]
发表于 2010-04-09 17:16 |只看该作者
{:3_196:}万一人家说的数组是一组数字的意思呢？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
samlumengjun

论坛徽章:
0
8楼 [报告]
发表于 2010-04-09 17:28 |只看该作者
万一人家说的数组是一组数字的意思呢？
A.com 发表于 2010-04-09 17:16



    你这样的假设没有任何意义,怎么不假设数组都是128位的整型?
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
noword2k

论坛徽章:
1
2015年迎新春徽章 日期:2015-03-04 09:50:28
9楼 [报告]
发表于 2010-04-09 17:57 |只看该作者
构建一个map，把数字一个一个的放入map里，直到找到有重复的。
因为是数字，所以根本不用进行hash。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
lenky0401

论坛徽章:
0
10楼 [报告]
发表于 2010-04-09 18:28 |只看该作者
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP