[演算法] Selection problem

708 views
Skip to first unread message

林立宇

unread,
Jan 14, 2015, 11:25:03 AM1/14/15
to zjh...@googlegroups.com
上星期演算法題庫班最後一堂
下課有同學問了一個關於selection problem的問題, 我來不及回答
這裡解釋一下
我們正課上課筆記寫的S1指的是所有小於 p 的元素所形成的集合
S2則是所有大於 p 的元素所形成的集合
所以S1不會只有左上角那一群, 同理S2也不會只有右下角那一群
上面這句應該是同學卡住的關鍵
因此要跟 k 比的並不是左上或右下的點數, 也不是 p, 而是|S1|
情況有以下兩種:
(1) 若 k <= |S1|, 則可prune掉S2
(2) 若 k > |S1|, 則可prune掉S1
這樣你應該就可以想通了

jeff 8231

unread,
Jan 18, 2015, 10:36:54 AM1/18/15
to zjh...@googlegroups.com
謝謝老師~~我懂了
老師抱歉 我昨天不小心拿到你上課的課本
今天下午還給大碩一樓櫃台的人了！

林立宇

unread,
Jan 20, 2015, 1:22:59 PM1/20/15
to zjh...@googlegroups.com
好滴, 謝啦~~
今天去上課時有拿到了

jeff 8231

unread,
Jan 29, 2015, 7:25:33 AM1/29/15
to zjh...@googlegroups.com
😄😄
Reply all
Reply to author
Forward
Message has been deleted
0 new messages