→ yr:這個做法好像是 O(K*min(R, C)) 04/29 00:25
※ 引述《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)?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.118.76