※ 引述《RockLee (Now of all times)》之铭言：
: 原始网址:
: 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 解法?
第一时间想到下面的解法 不知道有没有错
想让大家帮我看一下 XD
假设前 i 大的数字如下的 "X"
要找 i+1 就找下列 "O" 里面最大的
X ..... X X X X X X X X X X X X O
X ..... X X X X X O
X ..... X X X X O
.
.
X ..... X O
O
best case 应该是最大的都在第一行或第一列 只要比较 K-1 次
worst case 应该是分布为正三角形 O(logK * logK)?

这个做法好像是 O(K*min(R, C))