Her girişten sonra ortadaki skor
Görev tanımı
Problem
Skorlar birer birer geliyor. Her gelişten sonra o ana kadar görülen her şeyin ortadaki skorunu bildir. Skor sayısı çiftken ortadaki iki skordan düşük olanı bildir. Bildirimlerin listesini döndür ve her gelişten sonra bütün skorları yeniden sıralamaktan daha iyisini hedefle.
Örnekler
Input: scores = [5, 15, 1, 3]
Output: [5, 5, 5, 3]
Neden: dördü de geldikten sonra sıralı skorlar 1, 3, 5, 15 ve düşük orta 3
Input: scores = [2, 2, 2]
Output: [2, 2, 2]
Input: scores = []
Output: []
Neden: edge case: geliş yoksa bildirim de yok
İpuçları
0 / 3
Her gelişten sonra yeniden sıralamak bildirim başına n log n tutar. Orta yalnız alt yarının nerede bittiğine ve üst yarının nerede başladığına bağlı.
Skorları bir alt yarı ve bir üst yarıya böl. Sayı tekken fazla skoru alt yarı tuttuğu sürece bildirim, alt yarının en büyük skorudur.
Alt yarıyı bir max-heap'te, üst yarıyı bir min-heap'te tut. Her skoru ait olduğu tarafa push et, alt yarı birden fazla büyürse ya da üst yarı büyürse bir skoru karşıya taşı ve alt yarının tepesini bildir.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Çözüm
İki heap kalıbı sıralı düzeni hiç sıralamadan ortadan bölünmüş tutar: bir max-heap alt yarıyı tutar, böylece tepesi küçük skorların en büyüğüdür; bir min-heap de üst yarıyı tutar. Alt yarının bir skor büyük olmasına izin verilir; bu da tepesini tek sayı için ortadaki, çift sayı için düşük ortadaki skor yapar; tam olarak bildirilecek skor. Yeni bir skor, alt yarının tepesinden büyük değilse alt yarıya gider; karşıya tek bir taşıma da boyut kuralını geri getirir. Python'un heapq'su bir min-heap'tir, bu yüzden alt yarı negatiflenmiş skorları saklar. Her geliş O(log n) tutar; toplam zaman O(n log n), alan 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([])) # -> []Kodda değil de fikirde mi takıldın? İki heap: anlık medyan bunu anlatıyor.