原始網址:
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 解法?

想必跟1d 的case 有關係 !

感謝F大的連結 等明天精神好再來讀paper

感覺也是 median 的變形 ... @@

技巧類似，只是稍微複雜些。