Re: [理工] [DS]-台科大98-資工所
※ 引述《yesa315 (XD)》之銘言：
: http://www-o.ntust.edu.tw/~lib/pdf/Master/98/m980904.pdf
: 請問第4題的B怎麼寫
: 題目說不能合併3個成一個
: 我有想過是否先合併其中兩個 然後在兩個矩陣找中位數?
: 感謝
A, B, C三個已排序陣列，假設中位數分別是ma, mb, mc
在不失一般性的情況下，假設ma > mb > mc
在A中，大於ma的元素必大於ma, mb, mc的一半元素
在C中，小於mc的元素必小於ma, mb, mc的一半元素
在這兩種情況下，都不可能是中位數
因為他們分別大於3n/2個元素或是小於3n/2個元素。
如此問題就可以化簡成2/3的大小，然後遞迴做下去。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推
02/18 21:52, , 1F
02/18 21:52, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：