如何在二维排序数组中找到中值？例如

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]