Puntaje central tras cada entrada
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
Volver a ordenar tras cada llegada cuesta n log n por reporte. El centro solo depende de dónde termina la mitad inferior y dónde empieza la superior.
Divide los puntajes en una mitad inferior y una mitad superior. El reporte es el mayor puntaje de la mitad inferior, siempre que la mitad inferior se quede con el puntaje extra cuando la cantidad es impar.
Guarda la mitad inferior en un max-heap y la superior en un min-heap. Haz push de cada puntaje en el lado que le corresponde, mueve un puntaje al otro lado si la mitad inferior supera a la superior por más de uno o si la superior queda más grande, y reporta la cima de la mitad inferior.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Solución
El patrón de dos heaps (montículos) mantiene el orden dividido en el centro sin ordenar nunca: un max-heap guarda la mitad inferior, así que su cima es el mayor de los puntajes pequeños, y un min-heap guarda la mitad superior. La mitad inferior puede tener un puntaje más, lo que hace que su cima sea el central cuando la cantidad es impar y el central inferior cuando es par, justo el puntaje que hay que reportar. Un puntaje nuevo va a la mitad inferior salvo que sea mayor que su cima, y un solo movimiento al otro lado restablece la regla de tamaños. El heapq de Python es un min-heap, así que la mitad inferior guarda los puntajes negados. Cada llegada cuesta O(log n), así que el tiempo total es O(n log n) y el espacio es O(n).
import heapq
def middle_scores(scores):
low, high = [], [] # low: max-heap of negated scores, high: min-heap
reports = []
for s in scores:
if low and s > -low[0]:
heapq.heappush(high, s)
else:
heapq.heappush(low, -s)
if len(low) > len(high) + 1: # lower half too big
heapq.heappush(high, -heapq.heappop(low))
elif len(high) > len(low): # upper half too big
heapq.heappush(low, -heapq.heappop(high))
reports.append(-low[0]) # top of the lower half
return reports
print(middle_scores([5, 15, 1, 3])) # -> [5, 5, 5, 3]
print(middle_scores([2, 2, 2])) # -> [2, 2, 2]
print(middle_scores([])) # -> []¿Lo que te frena es la idea y no el código? Dos heaps: mediana acumulada lo explica.