| 网站首页 | 业界新闻 | 群组 | 人才 | 技术文章 | 下载频道 | 博客 | 代码贴 | 编程论坛
绝地游戏外挂辅助教学千里之行 始于足下
共有 1013 人关注过本帖
标题:经典算法题求解
只看楼主 收藏
某一天
Rank: 2
等 级:论坛游民
威 望:1
帖 子:33
专家分:77
注 册:2015-6-15
结帖率:0
  已结贴   问题点数:10  回复次数:4   
经典算法题求解
一个含n个元素的整数数组至少存在一个重复数,请编程实现,在O(n)时间内找出其中任意一个重复数。
搜索更多相关主题的帖子: 经典  元素  
2017-06-13 09:30
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:25
帖 子:3980
专家分:11326
注 册:2016-10-22
  得分:5 
记得上次遇到过一条相反的问题是找唯一不重复数的~这试试用哈希处理?~感觉可以编一张哈希表覆盖整个整数范围~

[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
2017-06-13 12:15
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:117
帖 子:1399
专家分:7072
注 册:2014-5-19
  得分:5 
我能够想到的最快方法是先归并排序,再线性检查相邻元素
2017-06-13 12:16
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:25
帖 子:3980
专家分:11326
注 册:2016-10-22
  得分:0 
回复 3楼 yangfrancis
归并排序的时间复杂度为o(n*log(n))~还是用哈希表合理~

[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
2017-06-13 13:37
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:117
帖 子:1399
专家分:7072
注 册:2014-5-19
  得分:0 
嗯。归并的时间复杂度不合要求。至于哈希表,我还不懂的
2017-06-13 22:24







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.258196 second(s), 8 queries.
Copyright©2004-2017, BCCN.NET, All Rights Reserved