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

[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
2017-06-13 12:15
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:112
帖 子:1364
专家分:6857
注 册:2014-5-19
  得分:5 
我能够想到的最快方法是先归并排序,再线性检查相邻元素
2017-06-13 12:16
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3656
专家分:10465
注 册:2016-10-22
  得分:0 
回复 3楼 yangfrancis
归并排序的时间复杂度为o(n*log(n))~还是用哈希表合理~

[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
2017-06-13 13:37
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:112
帖 子:1364
专家分:6857
注 册:2014-5-19
  得分:0 
嗯。归并的时间复杂度不合要求。至于哈希表,我还不懂的
2017-06-13 22:24







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

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