如何在二維排序數組中找到中值？例如

Question

假設你有一個數字矩陣，這些數字在行和列之間排序。

你怎麼找到的中位數。

我搜索了網，發現有很多喜歡的答案：

有一個算法來找出在O（LOGN）兩個排序陣列中位數 - 應用此n次。 我不認爲這是有道理的。

否則我得到了一些研究論文。這個問題似乎並不像爵士那樣。

誰能給我一個準確的算法？

Answer 1

複製二維數組一維數組使用循環，然後進行排序，然後找到中位數...二維陣列發現的唯一的行或列中值不統一，我認爲...多數民衆贊成我看來，這可能是錯誤的或者正確的...... !!

Answer 2

鑑於這是一個明智的行和列進行排序明智矩陣（m×n個），我們可以發現使用優先級隊列在澳中位數（M * N *日誌（M））。

的僞碼是，

PriorityQueue<Pair<int, int>> pq(m); 
//Pair<int, int> is the coordinate of the matrix element 
for i <- 0 to m 
    pq.add(Pair(i, 0)) 
count <- 0 
k = (m*n)/2 
Pair<int, int> xy 
while count < k: 
    count++ 
    xy <- pq.poll() 
    x <- xy.first 
    y <- xy.second 
    if y+1 < n: 
     pq.add(Pair(x, y+1)) 
return matrix[xy.first][xy.second]