İçeriğe geç

Skor akışında k. en büyük

Kolay#min-heap#top-k#data-stream~15 dk

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

Hedef zaman
O(n log k)
Hedef alan
O(k)

Kısıtlar

  • at least k scores are recorded at every add call

Kodda değil de fikirde mi takıldın? Akışta top-k bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır