如何取得一个很长的链表的前20大元素

edgar

ttres

iceviewer

似乎至少遍历一次链表，复杂度最低也是O(n)...

edgar

特设他

koolcoy

原帖由 iceviewer 于 2007-9-20 11:04 发表
似乎至少遍历一次链表，复杂度最低也是O(n)...

适当的优化可以降低常系数.

醉卧水云间

实验证明std::priority_queue是最快的。

foolishx

我有一个想法：只要遍历一次链表就行了。
但前提是这个作者应该对这个链表的数据的大小有一定的了解。它应该介于多大之间，这样才好用位图。
借助位图（bit map)来实现：假设这个数最大为4096。我只是打个比方，具体情况只要你了解这个想法，就应该可以知道如何变通了。

定义一个数组为：char a[4096]={0,};
然后遍历链表，假设第一个数据为12，那么就将a[12]置为'1'，如果第二个数为8，就将a[8]置为'1',当数为234时，就将a[234]置为'1'，依次类推。

遍历一遍链表之后，就会发现a[] = “010011111000011......1111100101010”这样的序列。想找最大的20个数就直接到数组的后面开始找20个‘1’的数组下标即可。

如果数据很多的话，应该比一般的算法效率高的。但是如果数的跨度太大，可能会浪费一些空间，比如最小数为1，最大为23456767 ，不过可以在这个基础上进行相应的优化，相信可以做到的。

unixpm

partial_sort， nth_element

fertiland

quicksort
如果超过内存限制而且数据不重复，具体操作编程珠玑上有讲

原帖由 foolishx 于 2007-9-21 22:27 发表
我有一个想法：只要遍历一次链表就行了。
但前提是这个作者应该对这个链表的数据的大小有一定的了解。它应该介于多大之间，这样才好用位图。
借助位图（bit map)来实现：假设这个数最大为4096。我只是打个比方 ...

[ 本帖最后由 fertiland 于 2007-9-23 21:01 编辑 ]

gtzzh

如果真的是相对20来讲很长的连表，那采用20个缓存进行插入排序，无可厚非了吧
毕竟程序到后期很容易稳定的，上万个数能不断的插入（除非元素大致升序）。随机数无所谓！