matrix - 2D の並べ替えられた配列で中央値を見つけるにはどうすればよいですか?

Question

行と列で並べ替えられた数値のマトリックスがあるとします。

中央値を見つける方法.

ネットで検索したところ、次のような多くの回答が見つかりました。

O（logn）で2つのソートされた配列の中央値を見つけるアルゴリズムがあります-これを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]