作者RockLee (Now of all times)
看板Prob_Solve
标题[问题] Google Interview Question (3)
时间Wed Feb 13 18:17:31 2013
原始网址:
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
1F：推 singlovesong:想必跟1d 的case 有关系 ! 02/13 20:14
3F：→ RockLee:感谢F大的连结 等明天精神好再来读paper 02/13 22:30
4F：推 yoco315:感觉也是 median 的变形 ... @@ 02/16 13:16
5F：推 FRAXIS:技巧类似，只是稍微复杂些。 02/17 11:37