|
锁定老帖子 主题：今天老大提出的一算法问题求解
精华帖 (0) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-07-01
最后修改：2011-07-01
一大小为10W的数组，存放的值为0-100W的整数（可能重复出现），对数组进行排序，要求时间复杂度为O(n)，并且尽量节约空间。
声明：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
用基数排序吧
|
| 返回顶楼 | |
