Kth Largest Element in a Stream

Q: k'ıncı en büyük eleman için neden max-heap değil de min-heap kullanılır?

k en büyük değerin en küçüğü hem yanıttır hem de yeni gelenin geçmesi gereken değerdir; k boyutundaki bir min-heap bu değeri tepede tutar. Her değerden oluşan bir max-heap en büyük değeri tepede tutar; bu nedenle k 'ıncı değere ulaşmak için her yeni gelişte k-1 değeri çıkarıp geri eklemek gerekir.

Q: Kth Largest Element in a Stream algoritmasının zaman karmaşıklığı nedir?

Her bir geliş O(log k) maliyetlidir: en üstteki değerle bir karşılaştırma ve k değerlik bir yığında en fazla bir kez aşağı süzülme. Yığını nums değerlerinden oluşturmak O(n log k) maliyetlidir; dolayısıyla tüm çalıştırma O((n + m) log k) zaman ve O(k) ek alan gerektirir.

KolayYığın (heap)

+10

Bir tam sayı akışı, nums içindeki değerlerle başlar. Ardından adds değerleri teker teker gelir. Her gelişten sonra, eşit değerleri ayrı ayrı sayarak, şimdiye kadar görülen tüm değerler arasındaki k. en büyük değeri kaydet. Kaydedilen değerleri, adds içindeki her değer için bir tane olacak şekilde sırayla döndür.

nums, en az k-1 değer içerir; bu nedenle ilk gelişten sonra seçilebilecek her zaman en az k değer bulunur.

Fonksiyon

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: bildirilecek sıra, en büyük değer için 1
numsinteger-array: akışta zaten bulunan değerler
addsinteger-array: gelen değerler, sırayla
Döndürürinteger-array: Her yeni gelişten sonra k'ncı en büyük değer

Kısıtlar

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums herhangi bir sırada olabilir ve eşit değerler ayrı değerler olarak sayılır.

Örnekler

Girdi: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Çıktı: [3, 5, 6, 6, 7]
Açıklama: 3'ten sonra, 7, 5, 3 ve 1 sayılarının üçüncü en büyüğü 3'tür. Ardından 9 onu 5'e, 6 onu 6'ya yükseltir, 2 hiçbir şeyi değiştirmez ve 8 onu 7'ye yükseltir (9, 8, 7).

Girdi: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Çıktı: [-2, 0, 0, 4]
Açıklama: k = 1 olduğunda yanıt şu ana kadarki en büyük değerdir: 0 gelene kadar -2, -1'den sonra da 0, ardından 4.

Ek soru

Değerler akıştan da çıkarılabilseydi aynı soruyu nasıl yanıtlardın?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Değerler akıştan asla çıkmaz; bu nedenle mevcut k. en büyük değerin altına düşen bir değer bir daha geri dönemez. Bir min-yığında yalnızca en büyük k değeri tut: tepedeki değer yanıttır ve her yeni değer bir karşılaştırmaya ve en fazla bir O(log k) yığın güncellemesine mal olur.

Her varıştan sonra sırala

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Listedeki her değeri tut. Her yeni değer geldiğinde listeyi artan sırada sırala ve tanım gereği k. en büyük değer olan length-k indeksini oku.

Her yeni değer geldiğinde en fazla n + m değer sıralanır; burada n ve m, nums ve adds dizilerinin uzunluklarıdır. Her birinden 10^4 tane olduğunda, toplamda yaklaşık 2 × 10^9 karşılaştırma yapılır.

Algoritma

nums'u values listesine kopyala.
adds içindeki her değeri values'a ekle.
values'u artan düzende sırala ve values[length-k] değerini kaydet.
Kaydedilen değerleri döndür.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

k en büyük değerin min-yığını

Sezgi

Bir değerin üzerinde k daha büyük değer bulunduğunda, bu durum akışın geri kalanı için de geçerli olur; bu nedenle şimdiye kadar görülen en büyük k değer önemlidir. Bunları bir min-yığında saklayın. Yığının tepesindeki değer, en büyük k değerin en küçüğüdür; bu da genel olarak k. en büyük değerdir.

x geldiğinde ve yığın dolu olduğunda, onu tepedeki değerle karşılaştırın. x daha büyük değilse, en büyük k değer arasında değildir ve hiçbir şey değişmez. Daha büyükse, tepedeki değer yığından çıkar: onu x ile değiştirin ve O(log k) sürede aşağı doğru süzdürün. Başlangıç değerleri de aynı işlemden geçer; bu nedenle nums, k değerinden uzun olabilir.

İlk örnekte, nums sonrasında yığında 7, 1 ve 5 bulunur ve tepede 1 vardır. Gelen 3, 1'in yerini alır ve tepede bulunan 3 ilk yanıttır.

Algoritma

Boş bir min-yığınla başlayın.
x eklemek için: yığında k değerinden az değer varsa x'i ekleyin. Aksi takdirde, x tepeden büyükse tepedeki değeri x ile değiştirin ve yığın düzenini yeniden sağlayın.
nums içindeki her değeri bu şekilde ekleyin.
adds içindeki her değer için onu ekleyin ve yığının tepesindeki değeri kaydedin.
Kaydedilen değerleri döndürün.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Tuzaklar ve uç durumlar

Tekrarları kaldırmak. 9, 6, 6, 6, 2 değerlerinin en büyük dördü 9, 6, 6 ve 6'dır. Bir küme ya da daha önce eklenmiş değerleri atlayan bir kontrol, üçüncü örnekte 6 yerine 2 döndürür.
Eklemeyi yapmadan önce yanıtı okumak. nums k-1 değer içerdiğinde yığın yalnızca ilk değer geldikten sonra dolar; bu yüzden önce ekle, ardından en üstteki değeri oku.
Sıralamadan sonra yanlış uçtan saymak. Artan sırada k. en büyük değer length-k indeksindedir; k-1 indeksi ise k. en küçük değeri tutar.
Varsayılan yığın sırasını kullanmak. C++'ın priority_queue ve Rust'ın BinaryHeap yapıları maksimum yığınlarıdır: greater<int> kullan ya da değerleri Reverse içine sar.

Sıkça sorulan sorular3

k'ıncı en büyük eleman için neden max-heap değil de min-heap kullanılır?

k en büyük değerin en küçüğü hem yanıttır hem de yeni gelenin geçmesi gereken değerdir; k boyutundaki bir min-heap bu değeri tepede tutar. Her değerden oluşan bir max-heap en büyük değeri tepede tutar; bu nedenle k'ıncı değere ulaşmak için her yeni gelişte k-1 değeri çıkarıp geri eklemek gerekir.

Kth Largest Element in a Stream algoritmasının zaman karmaşıklığı nedir?

Her bir geliş O(log k) maliyetlidir: en üstteki değerle bir karşılaştırma ve k değerlik bir yığında en fazla bir kez aşağı süzülme. Yığını nums değerlerinden oluşturmak O(n log k) maliyetlidir; dolayısıyla tüm çalıştırma O((n + m) log k) zaman ve O(k) ek alan gerektirir.

Akıştaki K. En Büyük Eleman sıralı bir listeyle çözülebilir mi?

Evet. Tüm değerleri sıralı tutun, her gelen değeri ikili aramayla yerine ekleyin ve sondan k konumdaki değeri okuyun. Arama O(log n) sürer, ancak ekleme noktasından sonraki değerleri kaydırmak, her gelen değer için O(n) sürer: 10^4 başlangıç değeri ve 10^4 gelen değer için yaklaşık 1.5 × 10^8 kaydırma.

def kthLargestStream(k, nums, adds):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Beklenen Çıktı

[3, 5, 6, 6, 7]