K-ésimo mayor en un stream de puntajes
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
Los puntajes por debajo del top k actual nunca vuelven a importar: un puntaje nuevo solo empuja el k-ésimo mayor hacia arriba, nunca hacia abajo. Así que nunca necesitas guardar más de k puntajes.
De los k puntajes que guardas, el que reportas es el menor de ellos. Un min-heap de tamaño k tiene ese valor en la cima.
En cada add, haz push del puntaje y, si el heap ahora tiene más de k elementos, haz pop del menor. La cima del heap es la respuesta.
- Tiempo objetivo
- O(n log k)
- Espacio objetivo
- O(k)
Restricciones
- at least k scores are recorded at every add call
Solución
El k-ésimo mayor de una colección que crece es el menor miembro de su top k, así que un min-heap limitado a k guarda exactamente la información necesaria. Cada puntaje nuevo entra con un push; si eso deja k + 1 puntajes, se hace pop del menor, porque ahora tiene al menos k puntajes por encima y nunca volverá a ser la respuesta. La cima del heap (montículo) es entonces el k-ésimo mayor. Ordenar toda la lista en cada llamada costaría O(n log n) por puntaje y guardaría todos los puntajes para siempre; el heap cuesta O(log k) por puntaje y O(k) de espacio sin importar cuánto dure el stream, que es el sentido del patrón top-k sobre un stream.
import heapq
class KthLargest:
def __init__(self, k, scores):
self.k = k
self.heap = [] # the k largest so far, smallest on top
for s in scores:
self.add(s)
def add(self, score):
heapq.heappush(self.heap, score)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # it has k scores above it now
return self.heap[0]
def run(k, scores, adds):
board = KthLargest(k, scores)
return [board.add(s) for s in adds]
print(run(3, [4, 5, 8, 2], [3, 5, 10, 9, 4])) # -> [4, 5, 5, 8, 8]
print(run(2, [0], [-1, 1, -2, -4, 3])) # -> [-1, 0, 0, 0, 1]
print(run(1, [], [-3, -2, -4, 0, 4])) # -> [-3, -2, -2, 0, 4]¿Lo que te frena es la idea y no el código? Top-k en un stream lo explica.