推 singlovesong:想必跟1d 的case 有關係 ! 02/13 20:14
→ RockLee:感謝F大的連結 等明天精神好再來讀paper 02/13 22:30
推 yoco315:感覺也是 median 的變形 ... @@ 02/16 13:16
推 FRAXIS:技巧類似，只是稍微複雜些。 02/17 11:37
原始網址:
http://www.careercup.com/question?id=15381730
題目:
Given a 2 dimensional (R*C) array. The rows and columns are sorted.
Find the Kth largest element from the 2-d array in most efficient way.
Can it be done in-place?
我能想到最快的方法是用 Balanced Tree (Ex. TreeMap in Java) 來解,
Time Complexity: O(K*logK).
要 in-place 來解我只有想到 in-place merge sort,
Time Complexity: O((R*C)*log(R*C)).
不過 in-place merge sort 完全沒用到 The rows and columns are sorted 這件事,
應該不會是一個好的答案.
不知道是否有比 O(K*logK) 更快的方法?
或是比較合理的 in-place 解法?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.88.12