Re: [問題] Google Interview Question (3)
看板Prob_Solve (計算數學 Problem Solving)作者fifer (大腦爆炸)時間11年前 (2013/04/15 03:21)推噓0(0推 0噓 1→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《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
→
04/29 00:25, , 1F
04/29 00:25, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
