算法--找一个unsorted array的largest and second largest 最 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

算法--找一个unsorted array的largest and second largest 最

算法--找一个unsorted array的largest and second largest 最# JobHunting - 待字闺中

i*92010-12-29 08:12

1 楼

大家都知道找最大值和最小值的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
什么技巧吗？

u*e2010-12-29 08:12

2 楼

merge sort?

【在 i**9 的大作中提到】

: 大家都知道找最大值和最小值的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
: 什么技巧吗？

D*h2010-12-29 08:12

3 楼

tournament tree

【在 i**9 的大作中提到】

: 大家都知道找最大值和最小值的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
: 什么技巧吗？

g*k2010-12-29 08:12

4 楼

这个类似吧。
两两比较得到(a1, a2), (b1, b2)，。。。
共比较n/2
比较a2和b2,
如果a2大，那么再比较a1和b2
如果b2大，那么再比较b1和a2
这一步比较2(n/2)次
一共比较3n/2

【在 i**9 的大作中提到】

: 大家都知道找最大值和最小值的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
: 什么技巧吗？

c*a2010-12-29 08:12

5 楼

build Heap

i*92010-12-29 08:12

6 楼

thanks, 总之，这个是要 extra memory, 这里有人提过不用extra memory ,我想了半
天也没想
出来，

【在 D***h 的大作中提到】

: tournament tree

x*p2010-12-29 08:12

7 楼

It only need two extra-memory. Start with (a1,a2) with a1>a2. Then for each
a3, ..., an, compare at most twice to (a1,a2) and do corresponding
replacement. So the total comparison is at most 1 + 2(n-2) = 2n - 3 = O(n).

i*92010-12-29 08:12

8 楼

using tournament tree only n+ lgn -2 times of comparison are needed

each
O(n).

【在 x*****p 的大作中提到】

: It only need two extra-memory. Start with (a1,a2) with a1>a2. Then for each
: a3, ..., an, compare at most twice to (a1,a2) and do corresponding
: replacement. So the total comparison is at most 1 + 2(n-2) = 2n - 3 = O(n).