Aby znaleźć medianę niesortowanej tablicy, możemy utworzyć stertę min w czasie O (nlogn) dla n elementów, a następnie możemy wyodrębnić jeden po drugim elementy n / 2, aby uzyskać medianę. Ale to podejście zajmie O (nlogn) czas.

Czy możemy zrobić to samo za pomocą jakiejś metody w czasie O (n)? Jeśli możemy, proszę powiedzieć lub zaproponować jakąś metodę.