一个查找算法题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一个查找算法题

一个查找算法题# JobHunting - 待字闺中

m*r2010-08-26 07:08

1 楼

【以下文字转载自 Programming 讨论区】
发信人: mindreader (摩登原始人), 信区: Programming
标题: 一个查找算法题
发信站: BBS 未名空间站 (Thu Aug 26 15:21:14 2010, 美东)
如何在一个大数组里的几个子数组中（序号不一定相连，比如2-30， 54-200）找出最
大的N个数，N<5,要求时间最快，不要求排序。
N=1 我的解法是利用下标把数分成奇偶两组，每次循环比较一次，然后比较最大的两个
数谁大，但是 N>2以后还能如此类似吗？

h*62010-08-26 07:08

2 楼

这种题用堆可以解吧。最大的 N 个数用最小堆，最小的 N 个数用最大堆。

f*52010-08-26 07:08

3 楼

N=1时直接求跟你的做法有什么区别？

【在 m********r 的大作中提到】

: 【以下文字转载自 Programming 讨论区】
: 发信人: mindreader (摩登原始人), 信区: Programming
: 标题: 一个查找算法题
: 发信站: BBS 未名空间站 (Thu Aug 26 15:21:14 2010, 美东)
: 如何在一个大数组里的几个子数组中（序号不一定相连，比如2-30， 54-200）找出最
: 大的N个数，N<5,要求时间最快，不要求排序。
: N=1 我的解法是利用下标把数分成奇偶两组，每次循环比较一次，然后比较最大的两个
: 数谁大，但是 N>2以后还能如此类似吗？

m*r2010-08-26 07:08

4 楼

快一些，循环次数少，流水线易优化。

【在 f*********5 的大作中提到】

: N=1时直接求跟你的做法有什么区别？

f*52010-08-26 07:08

5 楼

怎么快？
比较次数少？
举个例子说具体点吧，谢谢

【在 m********r 的大作中提到】

: 快一些，循环次数少，流水线易优化。

m*r2010-08-26 07:08

6 楼

循环次数少，每次下标加2，用两个指针分别从开始两个数和后面的比较，最后比较两
组的最大值。

【在 f*********5 的大作中提到】

: 怎么快？
: 比较次数少？
: 举个例子说具体点吧，谢谢