[問題] multiselection

[mqazz1 (無法顯示)]

consider the multiselection problem: giben a set S of n elements and a set K

of r ranks k1, k2,..., kr, find the k1-th, k2-th, ..., kr-th smallest elements

For example, if K={2,7,9,50}, the problem is to find the 2nd, 7th, 9th, 50th

smallest elements.

Give an O(nlogr) time algorithm to solve this problem


請問這題要怎麼解呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.116.67
→ suhorng:divide and conquer on r, with O(n) selection algorithm
請問s大的divide and conquer on r是怎麼應用到這個問題的@@?

===============

另外還想請問一些問題..這個是老師的解答 http://ppt.cc/Q(en

請問跑BFS的作用是什麼?

謝謝

※ 編輯: mqazz1          來自: 218.166.118.9        (11/08 20:19)
→ firejox:就是search而已 沒別的意思...