Problem oko zadatka medijana


#1

U vezi zadatka Medijana, uspeo sam da resim zadatak kada radim sa malim brojevima, ali u primerima su date ogromne promenljive i ne shvatam kako se one uopste mogu izracunati.

Link: https://petlja.org/biblioteka/r/problemi/zbirka-napredni-nivo/medijana


#2

Mozda ovo moze da ti pomogne. https://brilliant.org/wiki/median-finding-algorithm/


#3

E hvala, ja sam isao redom broj po broj dok nisam stigao do odgovarajuceg broja ili odgovarajuca dva broja.


#4

Koliko sam na brzinu stigao da probam, takođe su ograničenja takva da bi trebalo da možeš da sortiraš sve brojeve, dok god koristiš neki \mathcal{O}(N \log N) algoritam za sortiranje (quicksort, merge sort, …). Naravno, algoritmi koje je @milosh predložio imaju bolju složenost, ali možda je moguće rešiti zadatak na lakši način bez njih :slight_smile: