Saltar al contenido

K-ésimo mayor en un stream de puntajes

Fácil#min-heap#top-k#data-stream~15 min

La misión

Problema

Una tabla de posiciones muestra el k-ésimo puntaje más alto visto hasta ahora. Construye una clase KthLargest(k, scores) que parte de una lista de puntajes y tiene un solo método, add(score), que registra un puntaje nuevo y devuelve el k-ésimo mayor puntaje actual, contando duplicados. Cada llamada a add ocurre cuando ya se registraron al menos k puntajes, incluido el nuevo.

Ejemplos

Input:  k = 3, scores = [4, 5, 8, 2], then add 3, 5, 10, 9, 4
Output: [4, 5, 5, 8, 8]
Por qué: después de agregar 3, los puntajes son 2 3 4 5 8 y el tercero mayor es 4
Input:  k = 2, scores = [0], then add -1, 1, -2, -4, 3
Output: [-1, 0, 0, 0, 1]
Por qué: el primer add deja dos puntajes, así que el segundo mayor es el menor de ellos
Input:  k = 1, scores = [], then add -3, -2, -4, 0, 4
Output: [-3, -2, -2, 0, 4]
Por qué: caso límite: con k = 1, la respuesta es simplemente el máximo hasta ahora

Pistas

0 / 3

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

Restricciones

  • at least k scores are recorded at every add call

¿Lo que te frena es la idea y no el código? Top-k en un stream lo explica.

Python 3Ctrl+Enter ejecuta