Pontuação do meio após cada entrada
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
Ordenar tudo de novo a cada chegada custa n log n por resultado. O meio só depende de onde a metade inferior termina e a metade superior começa.
Divida as pontuações em uma metade inferior e uma metade superior. O resultado é a maior pontuação da metade inferior, desde que a metade inferior fique com a pontuação extra quando a contagem for ímpar.
Guarde a metade inferior em um max-heap e a metade superior em um min-heap. Insira cada pontuação no lado a que ela pertence, mova uma pontuação de lado se a metade inferior ficar com mais de uma a mais ou se a metade superior ficar maior, e informe o topo da metade inferior.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Solução
O padrão de dois heaps mantém a ordem dividida no meio sem nunca ordenar: um max-heap guarda a metade inferior, então o seu topo é a maior das pontuações baixas, e um min-heap guarda a metade superior. A metade inferior pode ter uma pontuação a mais, o que faz do seu topo o meio para uma contagem ímpar e a menor das duas do meio para uma contagem par, exatamente a pontuação a informar. Uma pontuação nova vai para a metade inferior, a menos que seja maior que o topo dela, e um movimento de lado restaura a regra de tamanho. O heapq do Python é um min-heap, então a metade inferior guarda pontuações negadas. Cada chegada custa O(log n), então o tempo é O(n log n) no total e o espaço é O(n).
import heapq
def middle_scores(scores):
low, high = [], [] # low: max-heap of negated scores, high: min-heap
reports = []
for s in scores:
if low and s > -low[0]:
heapq.heappush(high, s)
else:
heapq.heappush(low, -s)
if len(low) > len(high) + 1: # lower half too big
heapq.heappush(high, -heapq.heappop(low))
elif len(high) > len(low): # upper half too big
heapq.heappush(low, -heapq.heappop(high))
reports.append(-low[0]) # top of the lower half
return reports
print(middle_scores([5, 15, 1, 3])) # -> [5, 5, 5, 3]
print(middle_scores([2, 2, 2])) # -> [2, 2, 2]
print(middle_scores([])) # -> []Travou na ideia, e não no código? Dois heaps: mediana contínua explica isso.