Para encontrar a mediana de uma matriz não classificada, podemos fazer um min-heap em O (nlogn) tempo para n elementos, e então podemos extrair um por um elementos n / 2 para obter a mediana. Mas essa abordagem levaria tempo O (nlogn).

Podemos fazer o mesmo por algum método no tempo O (n)? Se pudermos, então, por favor, diga ou sugira algum método.