matrix - 如何在二维排序数组中找到中位数？

Question

假设您有一个按行和列排序的数字矩阵。

你如何找到中位数。

我在网上搜索并找到了很多答案，例如：

有一种算法可以在 O(logn) 中找到两个排序数组的中位数 - 应用这个 n 次。我认为这没有任何意义。

否则我会得到一些研究论文。不过，这个问题似乎并不那么有趣。

谁能给我一个精确的算法？

Answer 1

鉴于它是按行和按列排序的矩阵 (mxn)，我们可以使用优先队列找到 O(m*n*log(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]