Skor akışında k. en büyük
Görev tanımı
Problem
Bir liderlik tablosu şimdiye kadar görülen k. en yüksek skoru gösteriyor. Bir skor listesinden başlayan ve tek bir metodu (method), add(score), olan bir KthLargest(k, scores) sınıfı kur; bu metot yeni bir skoru kaydeder ve tekrarları sayarak mevcut k. en büyük skoru döndürür. Her add çağrısı, yenisi dahil en az k skor kaydedilmişken gerçekleşir.
Örnekler
Input: k = 3, scores = [4, 5, 8, 2], then add 3, 5, 10, 9, 4
Output: [4, 5, 5, 8, 8]
Neden: 3 eklendikten sonra skorlar 2 3 4 5 8 ve üçüncü en büyük 4
Input: k = 2, scores = [0], then add -1, 1, -2, -4, 3
Output: [-1, 0, 0, 0, 1]
Neden: ilk add iki skor yapar, bu yüzden ikinci en büyük ikisinden küçük olanı
Input: k = 1, scores = [], then add -3, -2, -4, 0, 4
Output: [-3, -2, -2, 0, 4]
Neden: edge case: k = 1 ile cevap basitçe şimdiye kadarki maksimum
İpuçları
0 / 3
Mevcut ilk k'nın altındaki skorlar bir daha asla önemli olamaz: yeni bir skor k. en büyüğü yalnız yukarı iter, asla aşağı değil. Yani hiçbir zaman k'dan fazla skor tutmana gerek yok.
Tuttuğun k skor arasında bildirdiğin, onların en küçüğü. k boyutundaki bir min-heap'in tepesinde bu değer var.
add'de skoru push et; heap artık k'dan fazla öğe tutuyorsa en küçüğü pop et. Heap'in tepesi cevaptır.
- Hedef zaman
- O(n log k)
- Hedef alan
- O(k)
Kısıtlar
- at least k scores are recorded at every add call
Çözüm
Büyüyen bir koleksiyonun k. en büyüğü, onun ilk k'sının en küçük üyesidir; bu yüzden k ile sınırlanmış bir min-heap tam olarak gereken bilgiyi tutar. Her yeni skor push edilir; bu k + 1 skor yaparsa en küçüğü pop edilir, çünkü artık üstünde en az k skor vardır ve bir daha asla cevap olmayacaktır. Heap'in tepesi o zaman k. en büyüktür. Her çağrıda bütün listeyi sıralamak skor başına O(n log n) tutar ve her skoru sonsuza kadar saklardı; heap ise akış (stream) ne kadar uzun sürerse sürsün skor başına O(log k) ve O(k) alan tutar; bir akış üzerinde top-k kalıbının amacı da bu.
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]Kodda değil de fikirde mi takıldın? Akışta top-k bunu anlatıyor.