Revizia anterioară Revizia următoare
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.
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.