Medianator P92501
Implementeu una classe Medianator que mantinguin una col·lecció de naturals i ofereixi operacions per afegir un natural (amb possibles repetits) i consultar la mediana dels naturals afegits fins al moment.
Recordeu que la mediana d’n elements és aquell que es trobaria a la posició ⌊ (n + 1)/2 ⌋ (començant per 1) si estiguessin ordenats. Així, la mediana de cinc elements és el tercer més petit i la mediana de sis elements també és el tercer més petit.
Descarregueu-vos el fitxer code.py. Aquest ja conté la interfície de la classe i un programa principal de proves que la fa servir.
Les vostres operacions han de tenir cost logarítmic. Comproveu els possibles errors amb assercions. Documenteu i especifiqueu el vostre codi adequadament.
Pista: Penseu a classificar els elements en dos grups, fent servir estructures de dades que permetin traslladar elements particulars entre els dos grups amb cost logarítmic.
Input
add 30 median add 50 median add 10 median add 10 median add 10 median add 60 median add 15 median
Output
30 30 30 10 10 10 15
Input
add 10 median add 60 median add 90 median add 66 median add 0 median add 80 median add 77 median add 12 median
Output
10 10 60 60 60 60 66 60
Input
add 1 add 2 add 3 add 4 add 5 median add 6 median
Output
3 3
- Author
- Jordi Petit
- Language
- Catalan
- Official solutions
- Python
- User solutions
- Python