今天老大提出的一算法问题求解

醉倚西风 · 发表于 2011-8-7 10:49

一大小为10W的数组，存放的值为0-100W的整数（可能重复出现），对数组进行排序，要求时间复杂度为O(n)，并且尽量节约空间。

Jethro · 发表于 2011-8-7 10:49

一大小为10W的数组，存放的值为0-100W的整数（可能重复出现），求一时间复杂度为O(n)的算法，并且尽量节约空间。

求解什么呢？

找不到我 · 发表于 2011-8-7 10:50

一大小为10W的数组，存放的值为0-100W的整数（可能重复出现），求一时间复杂度为O(n)的算法，并且尽量节约空间。

求解什么呢？

不好意思，已经修改了

找不到我 · 发表于 2011-8-7 10:50

一大小为10W的数组，存放的值为0-100W的整数（可能重复出现），对数组进行排序，要求时间复杂度为O(n)，并且尽量节约空间。

http://www.comp.nus.edu.sg/~xuji ... orting/chapter3.htm
但是有限制条件

其它基于比较的排序算法有个下界O(nlogn).

曾经的小孩 · 发表于 2011-8-7 10:50

基数排序。。。

走就走吧 · 发表于 2011-8-7 10:50

o(n)....

Jethro · 发表于 2011-8-7 10:50

csuyux 写道
一大小为10W的数组，存放的值为0-100W的整数（可能重复出现），对数组进行排序，要求时间复杂度为O(n)，并且尽量节约空间。

开个100W的数组A[100W],默认值为0。
第一遍扫描10W的数组DATA[10W]， A[DATA[i]]+=1
第二遍扫描100W的数组，去掉A[i]=0的项。。

走失的猫咪 · 发表于 2011-8-7 10:50

采用位排序不知道可不可行。

开一个长度为100w+1的数组 bitArray[100w+1];
循环10w的数组，把各个数字num对应的bitArray[num]设为true；
那么在这个时候，bitArray的各个索引就是排序以后的数组了。时间复杂度O(n);
循环bitArray，把value为true的索引拿出来，得到的就是排序的，去重复的数组。

fl · 发表于 2011-8-7 10:50

利用布隆过滤器排序，http://pisces-java.iteye.com/blog/766745

feiguo · 发表于 2011-8-7 10:51

用基数排序吧

帐号		自动登录	找回密码
密码			成为会员