Допустим, у вас есть матрица чисел, отсортированных как по строкам, так и по столбцам.
Как найти медиану.
Я искал в сети и нашел много ответов, таких как:
Существует алгоритм нахождения медианы двух отсортированных массивов за O(logn) — примените его n раз. Я не думаю, что это имеет смысл.
Или же я получаю некоторые исследовательские работы. Однако проблема не кажется такой уж фантастической.
Может ли кто-нибудь дать мне точный алгоритм?
Учитывая, что это матрица, отсортированная по строкам и столбцам (m x n), мы можем найти медиану в O (m * n * log (m)), используя Priority Queue.
Псевдокод,
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]
"algorithm to find median of two sorted arrays ..."? - person Bernhard Barker schedule 10.02.2013