锁定老帖子 主题:今天老大提出的一算法问题求解
精华帖 (0) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (1)
|
|
---|---|
作者 | 正文 |
发表时间:2011-07-01
最后修改:2011-07-01
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2011-07-01
csuyux 写道 一大小为10W的数组,存放的值为0-100W的整数(可能重复出现),求一时间复杂度为O(n)的算法,并且尽量节约空间。 求解什么呢? |
|
返回顶楼 | |
发表时间:2011-07-01
aswang 写道 csuyux 写道 一大小为10W的数组,存放的值为0-100W的整数(可能重复出现),求一时间复杂度为O(n)的算法,并且尽量节约空间。
求解什么呢? 不好意思,已经修改了 |
|
返回顶楼 | |
发表时间:2011-07-01
最后修改:2011-07-01
csuyux 写道 一大小为10W的数组,存放的值为0-100W的整数(可能重复出现),对数组进行排序,要求时间复杂度为O(n),并且尽量节约空间。
http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/commonalg/sort/internal_sorting/chapter3.htm 但是有限制条件 其它基于比较的排序算法有个下界O(nlogn). |
|
返回顶楼 | |
发表时间:2011-07-01
最后修改:2011-07-03
基数排序。。。
|
|
返回顶楼 | |
发表时间:2011-07-02
最后修改:2011-07-02
o(n)....
|
|
返回顶楼 | |
发表时间:2011-07-02
csuyux 写道 一大小为10W的数组,存放的值为0-100W的整数(可能重复出现),对数组进行排序,要求时间复杂度为O(n),并且尽量节约空间。
开个100W的数组A[100W],默认值为0。 第一遍扫描10W的数组DATA[10W], A[DATA[i]]+=1 第二遍扫描100W的数组,去掉A[i]=0的项。。 |
|
返回顶楼 | |
发表时间:2011-07-02
采用位排序不知道可不可行。
开一个长度为100w+1的数组 bitArray[100w+1]; 循环10w的数组,把各个数字num对应的bitArray[num]设为true; 那么在这个时候,bitArray的各个索引就是排序以后的数组了。时间复杂度O(n); 循环bitArray,把value为true的索引拿出来,得到的就是排序的,去重复的数组。 |
|
返回顶楼 | |
发表时间:2011-07-02
最后修改:2011-07-02
利用布隆过滤器排序,http://pisces-java.iteye.com/blog/766745
|
|
返回顶楼 | |
发表时间:2011-07-02
用基数排序吧
|
|
返回顶楼 | |