悠悠博客 (讨论区存档) — 技术永无止尽，未来事在人为

先排序再找.

[quote]原帖由 [i]tigerajs[/i] 于 2008-6-28 16:59 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8692756&ptid=1182942][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
n是奇数,要求采用尽量少的比较符号 [/quote]
楼主什么意思？能不能说的清楚点？

[quote]原帖由 [i]tigerajs[/i] 于 2008-6-28 00:59 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8692756&ptid=1182942][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
n是奇数,要求采用尽量少的比较符号 [/quote]

类似于快速排序。n个数中找第k小的元素：随便取一个元素（比如第一个）作“标尺”，把所有小于它的搞到它左边，大于等于它的放到它右边。设左边有m个元素。

如果m=k-1，那么返回标尺；
如果m<k-1就在右边的n-m-1个数中找第k-m-1小的元素；
如果m>=k就在左边m个数中找第k小的元素。

平均时间复杂度 O(n).

另外算法导论里有保证时间复杂度是O(n)的选择第k小元素的算法，不过那个常熟系数相对比较大。

最小堆或最大堆

[quote]原帖由 [i]cugb_cat[/i] 于 2008-6-28 19:26 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8693460&ptid=1182942][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
最小堆或最大堆 [/quote]
难道要堆排序？这个建堆开销就很大了
还是4楼说的第k小算法的开销最小

[quote]原帖由 [i]tyc611[/i] 于 2008-6-29 11:06 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8695891&ptid=1182942][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]

难道要堆排序？这个建堆开销就很大了
还是4楼说的第k小算法的开销最小 [/quote]
不是，排序的开销比找第N顺序数开销大很多，好像算法导论第9章写了～

[quote]原帖由 [i]cugb_cat[/i] 于 2008-6-29 11:31 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8696045&ptid=1182942][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]

不是，排序的开销比找第N顺序数开销大很多，好像算法导论第9章写了～ [/quote]
哪怎么使用堆来解决？

回复 #3 77h2_eleven 的帖子

就是假设有2n-1个数,怎么样找出第n大的数字,也就是找中间值