经典算法题求解 - 编程论坛

#2

九转星河2017-06-13 12:15

记得上次遇到过一条相反的问题是找唯一不重复数的~这试试用哈希处理？~感觉可以编一张哈希表覆盖整个整数范围~

#3

yangfrancis2017-06-13 12:16

我能够想到的最快方法是先归并排序，再线性检查相邻元素

#4

九转星河2017-06-13 13:37

回复 3楼 yangfrancis

归并排序的时间复杂度为o(n*log(n))~还是用哈希表合理~

#5

yangfrancis2017-06-13 22:24

嗯。归并的时间复杂度不合要求。至于哈希表，我还不懂的

#6

九转星河2018-03-29 02:05

看数据范围有多大了,如果考虑哈希冲突的话,可以先开一个100w规模数组对尾部五个位的数字进行基数排序(注意用链表动态分配空间),或者正常来说普通基数排序后5位也可以~通常int不会超过11位,然后对前6个位进行哈希检测(就是总是一次能搜到结果,如果有重复的就输出那个重复数可以了),内判断有没有重复的~时间复杂度完全有可能在o(n)实现

~

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