K-ésima maior pontuação em um stream
A missão
Problema
Um placar mostra a k-ésima maior pontuação vista até agora. Crie uma classe KthLargest(k, scores) que parte de uma lista de pontuações e tem um único método, add(score), que registra uma pontuação nova e retorna a k-ésima maior pontuação atual, contando duplicados. Toda chamada a add acontece quando pelo menos k pontuações já foram registradas, incluindo a nova.
Exemplos
Input: k = 3, scores = [4, 5, 8, 2], then add 3, 5, 10, 9, 4
Output: [4, 5, 5, 8, 8]
Por quê: depois de adicionar 3, as pontuações são 2 3 4 5 8 e a terceira maior é 4
Input: k = 2, scores = [0], then add -1, 1, -2, -4, 3
Output: [-1, 0, 0, 0, 1]
Por quê: o primeiro add forma duas pontuações, então a segunda maior é a menor delas
Input: k = 1, scores = [], then add -3, -2, -4, 0, 4
Output: [-3, -2, -2, 0, 4]
Por quê: edge case: com k = 1, a resposta é simplesmente o máximo até agora
Dicas
0 / 3
Pontuações abaixo do top k atual nunca mais importam: uma pontuação nova só empurra a k-ésima maior para cima, nunca para baixo. Então você nunca precisa guardar mais de k pontuações.
Entre as k pontuações que você guarda, a que você informa é a menor delas. Um min-heap de tamanho k tem esse valor no topo.
No add, insira a pontuação e, se o heap passar a ter mais de k itens, extraia o menor. O topo do heap é a resposta.
- Tempo-alvo
- O(n log k)
- Espaço-alvo
- O(k)
Restrições
- at least k scores are recorded at every add call
Solução
A k-ésima maior de uma coleção que cresce é o menor membro do seu top k, então um min-heap limitado a k guarda exatamente a informação necessária. Cada pontuação nova é inserida; se isso resultar em k + 1 pontuações, a menor é extraída, porque agora ela tem pelo menos k pontuações acima dela e nunca mais será a resposta. O topo do heap é então a k-ésima maior. Ordenar a lista inteira a cada chamada custaria O(n log n) por pontuação e guardaria todas as pontuações para sempre; o heap custa O(log k) por pontuação e O(k) de espaço, não importa quanto tempo o stream dure, e essa é justamente a razão de ser do padrão top-k em um 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]Travou na ideia, e não no código? Top-k em um stream explica isso.