[問題] Google Interview Question (3)
看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間11年前 (2013/02/13 18:17)推噓4(4推 0噓 1→)留言5則, 4人參與討論串1/2 (看更多)
原始網址:
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
推
02/13 20:14, , 1F
02/13 20:14, 1F
推
02/13 21:17, , 2F
02/13 21:17, 2F
→
02/13 22:30, , 3F
02/13 22:30, 3F
推
02/16 13:16, , 4F
02/16 13:16, 4F
推
02/17 11:37, , 5F
02/17 11:37, 5F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
