Pular para o conteúdo

Pontuação do meio após cada entrada

Fácil#two-heaps#streaming~20 min

A missão

Problema

As pontuações chegam uma de cada vez. Depois de cada chegada, informe a pontuação do meio de tudo o que foi visto até agora. Quando o número de pontuações for par, informe a menor das duas pontuações do meio. Retorne a lista de resultados e tente fazer melhor do que ordenar todas as pontuações de novo a cada chegada.

Exemplos

Input:  scores = [5, 15, 1, 3]
Output: [5, 5, 5, 3]
Por quê: depois que as quatro chegam, as pontuações ordenadas são 1, 3, 5, 15, e a menor do meio é 3
Input:  scores = [2, 2, 2]
Output: [2, 2, 2]
Input:  scores = []
Output: []
Por quê: edge case: sem chegadas, não há resultados

Dicas

0 / 3

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

Travou na ideia, e não no código? Dois heaps: mediana contínua explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado