原始网址:
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 的变形 ... @@

技巧类似，只是稍微复杂些。