| 网站首页 | 业界新闻 | 群组 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
雷速体育发帖软件开发QQ118000023C语言培训|一对一辅导|零基础学编程LightningChart 快速先进的.Net图表控件
共有 1468 人关注过本帖
标题:经典算法题求解
只看楼主 收藏
某一天
Rank: 2
等 级:论坛游民
威 望:1
帖 子:33
专家分:77
注 册:2015-6-15
结帖率:0
  已结贴   问题点数:10  回复次数:5   
经典算法题求解
一个含n个元素的整数数组至少存在一个重复数,请编程实现,在O(n)时间内找出其中任意一个重复数。
搜索更多相关主题的帖子: 经典  元素  
2017-06-13 09:30
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:45
帖 子:4902
专家分:13909
注 册:2016-10-22
  得分:5 
记得上次遇到过一条相反的问题是找唯一不重复数的~这试试用哈希处理?~感觉可以编一张哈希表覆盖整个整数范围~

[code]/*~个性签名:弟弟的妹妹叫妹妹,弟弟的姐姐叫姐姐~ 2018-06-18更~*/[/code]
2017-06-13 12:15
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:130
帖 子:1488
专家分:7495
注 册:2014-5-19
  得分:5 
我能够想到的最快方法是先归并排序,再线性检查相邻元素
2017-06-13 12:16
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:45
帖 子:4902
专家分:13909
注 册:2016-10-22
  得分:0 
回复 3楼 yangfrancis
归并排序的时间复杂度为o(n*log(n))~还是用哈希表合理~

[code]/*~个性签名:弟弟的妹妹叫妹妹,弟弟的姐姐叫姐姐~ 2018-06-18更~*/[/code]
2017-06-13 13:37
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:130
帖 子:1488
专家分:7495
注 册:2014-5-19
  得分:0 
嗯。归并的时间复杂度不合要求。至于哈希表,我还不懂的
2017-06-13 22:24
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:45
帖 子:4902
专家分:13909
注 册:2016-10-22
  得分:0 
看数据范围有多大了,如果考虑哈希冲突的话,可以先开一个100w规模数组对尾部五个位的数字进行基数排序(注意用链表动态分配空间),或者正常来说普通基数排序后5位也可以~通常int不会超过11位,然后对前6个位进行哈希检测(就是总是一次能搜到结果,如果有重复的就输出那个重复数可以了),内判断有没有重复的~时间复杂度完全有可能在o(n)实现~

[此贴子已经被作者于2018-3-29 02:06编辑过]


[code]/*~个性签名:弟弟的妹妹叫妹妹,弟弟的姐姐叫姐姐~ 2018-06-18更~*/[/code]
2018-03-29 02:05







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

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