|
以文本方式查看主题 - 计算机科学论坛 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- 算法设计与分析习题谁会做 (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=27779) |
|
-- 作者：tonyt68ie -- 发布时间：2/25/2006 9:50:00 PM -- 算法设计与分析习题谁会做 给定数组A=(98,31,22,44,37,9) 试用分治法求其第二小元素 (要求使用SELECT算法) 请高手给出正确解答过程 |
|
-- 作者：erxuan -- 发布时间：3/12/2006 3:07:00 AM --
这个在算法导论Introduction to Algorithms的chapter9, Median and Order Statistic的section-2有详细算法给出。基本思路和quicksort一样。找第K个最小元素思路如下 FindKMedian( A, K ) 1.Pick randomly a number a from A = {a1, ..., an}. 2.Partition the n numbers into two sets: S - all the numbers smaller than a B - all the numbers bigger than a 3.If |S| = K-1 then a is the required K-median. Return a 4.If |S| < K-1 then the K-median lies somewhere in B. Call recursively to FindKMedian( B, K - |S| - 1 ) Else, call recursively to FindKMedian( S, K ). |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
31.000ms |