Pular para o conteúdo

K-ésima maior pontuação em um stream

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

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

Tempo-alvo
O(n log k)
Espaço-alvo
O(k)

Restrições

  • at least k scores are recorded at every add call

Travou na ideia, e não no código? Top-k em um stream explica isso.

Python 3Ctrl+Enter executa