Saltar al contenido

Puntaje central tras cada entrada

Fácil#two-heaps#streaming~20 min

La misión

Problema

Los puntajes llegan uno por uno. Después de cada llegada, reporta el puntaje central de todo lo visto hasta ahora. Cuando la cantidad de puntajes es par, reporta el menor de los dos puntajes centrales. Devuelve la lista de reportes, y apunta a algo mejor que volver a ordenar todos los puntajes después de cada llegada.

Ejemplos

Input:  scores = [5, 15, 1, 3]
Output: [5, 5, 5, 3]
Por qué: tras llegar los cuatro, los puntajes ordenados son 1, 3, 5, 15, y el central inferior es 3
Input:  scores = [2, 2, 2]
Output: [2, 2, 2]
Input:  scores = []
Output: []
Por qué: caso límite: sin llegadas no hay reportes

Pistas

0 / 3

Tiempo objetivo
O(n log n)
Espacio objetivo
O(n)

¿Lo que te frena es la idea y no el código? Dos heaps: mediana acumulada lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio