blog/problema-saptamanii-stream-solutie

Problema saptamanii - Stream (Solutie)

Scrie aici despre blog/problema-saptamanii-stream-solutie

Am gasit problema in cartea "Introduction to Algorithms: A Creative Approach" de Udi Manber. Pana sa vad cerinta din cartea respectiva credeam ca problema se poate face doar in O(n log k) daca esti obligat sa folosesti doar O(k) memorie, dar citind-o mi-am dat seama ca nu e greu sa scoti o solutie in O(n) timp si O(k) spatiu.

Stefan Istrate,

Cei ce au rezolvat corect problema sunt urmatorii: Stefan Istrate, Andrei Marius Teodorescu, Adrian Vladu, Marius Pungaru, Marius Buzea, Daniel Pasaila si Alexandru Mosoi.
 
Va dau si solutia:
_Pastram un sir A in care avem cele mai mici k numere din stream pana la momentul curent. Apoi la fiecare pas citim k noi elemente din stream in sirul B. Acum in sirul C punem elementele din ambele siruri si aplicam algoritmul de gasire a medianei algoritm ce va avea complexitate O(k), vom pastra in A elementele din C mai mici sau egale cu mediana. Astfel obtinem un algoritm de complexitate O(n) ca timp si O(k) ca spatiu._