从100万个整数里找出100个最大的数

lizhaochai 2008-07-25 03:44:14

从100万个整数里找出100个最大的数（用哪种算法效率高）

...全文

7773 59 打赏收藏转发到动态举报

写回复

用AI写文章

59 条回复

切换为时间正序

请发表友善的回复…

发表回复

itkingdom 2011-10-15

打赏
举报

都是高人啊，学习了，呵呵

贾囧雷 2011-09-26

打赏
举报

很容易，胜者树

jjqldyt 2011-04-27

打赏
举报

8楼的这个算法比27楼的一点都不差啊，我个人感觉，有人给分析下么

template< class T >
void solution_3( T BigArr[], T ResArr[] )
{
//取最前面的一万个
memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );
//标记是否发生过交换
bool bExchanged = true;
//遍历后续的元素
for( int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; ++i )
{
int idx;
//如果上一轮发生过交换
if( bExchanged )
{
//找出ResArr中最小的元素
int j;
for( idx = 0, j = 1; j < RES_ARR_SIZE; ++j )
{
if( ResArr[idx] > ResArr[j] )
idx = j;
}
}
//这个后续元素比ResArr中最小的元素大，则替换。
if( BigArr[i] > ResArr[idx] )
{
bExchanged = true;
ResArr[idx] = BigArr[i];
}
else
bExchanged = false;
}
}
上面的代码使用了一个布尔变量bExchanged标记是否发生过交换，这是一个前文没有谈到的优化手段——用以标记元素交换的状态，可以大大减少查找ResArr中最小元素的次数。也对solution_3进行测试一下，结果用时2.0秒左右（不使用bExchanged则高达32分钟），远小于solution_2的用时

minounou 2010-10-17

打赏
举报

【编程之美】里面有这道题的5种解法

yuzsrzz 2010-01-17

打赏
举报

顶

。。。。。。。。。。。

caohoujie 2008-08-05

打赏
举报

建10000个元素的堆才是正解，其他回答都是垃圾

hemdacker 2008-07-27

打赏
举报

mark

tangshuiling 2008-07-27

打赏
举报

mark!

zxcv8356631 2008-07-27

打赏
举报

把值处理后为key(保证大的书key大) 让后建哈希表？行不？

guolihui112 2008-07-27

打赏
举报

恩 27楼的答案不错不过小弟有一下疑问：
“则插入链表中,同时挤掉最小的数”，这其中最小的数如何判断。尽管“开始分配101个节点,用一个指针记录那个空节点”，但是这个空结点是什么内容？上次新插入的值，还是插入后数组中最小的值？
我的想法：获得最小的数有以下方案
1.插入一个数后，重新排序。这样每次插入一个数都要排序，看似效率不高
2.插入一个数后，将数组中数与新插入的数比较，更新最小值。不过每次插入都要比较，
3.每100个数作为一组，设置两个指针，一个指向旧的100那组最小值（排过序了,所以没什么消耗),一个指向新增加的数中最小值，在每次插入一个新数时候更新两个指针，这样这100个数中最小值即为两个指针指向数的最小值。在每插入100个数后重新排序，作为一个新组重新开始。这种方式看起来比上面两个虽然耗了点空间，不过应该提升了点时间效率。
不知道还有没有别的方案？

devoc 2008-07-27

打赏
举报

[Quote=引用 27 楼 A_B_C_ABC 的回复:]
取前100个数排序,放入链表中.依次取后面的数与100个数的最小数比较,若取到的数比最小数大,则插入链表中,同时挤掉最小的数.这个过程中使用的链表,因为大小是固定的,所以只需要一开始分配101个节点,用一个指针记录那个空节点,则在整个插入删除过程序中,可以不涉及到内存分配.
[/Quote]
这个感觉不错

iambic 2008-07-27