Kth Largest Element in an Array

Q: Dizideki K. En Büyük Elemanın zaman karmaşıklığı nedir?

Sıralama O(n log n) zaman alır. Boyutu k olan bir min-yığın O(n log k) zaman ve O(k) bellek gerektirir. Rastgele bir pivot kullanan Quickselect, ortalama olarak O(n) zaman alır; en kötü durumdaki O(n²) karmaşıklığına ise rastgele pivot nedeniyle rastlamak çok düşük bir olasılıktır.

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

Yığın, şimdiye kadar görülen en büyük k değeri saklar ve karşılaştırıp çıkarmanız gereken değer bunların en küçüğüdür. Bir min-heap bu değeri en üstte tutar. Bir max-heap yalnızca tüm n değerleri içine koyup k-1 kez pop ederseniz işe yarar; bu da O(n) bellek gerektirir.

Q: k'ncı en büyük eleman için yığın mı yoksa quickselect mi kullanmalıyım?

Quickselect ortalama olarak daha hızlıdır: O(n) ; ancak tüm değerlerin bellekte bulunmasını gerektirir ve onları yeniden sıralar. Heap, kötü bir en kötü durum olmaksızın O(n log k) karmaşıklığındadır ve değerler teker teker geldiğinde ve hepsini saklayamadığınızda işe yarar. Bir mülakatta ikisini de açıklayın ve takip sorusunda isteneni kodlayın.

OrtaYığın (heap)Sıralama

+10

Bir tamsayı dizisi nums ve bir tamsayı k veriliyor. nums içindeki k. en büyük değeri döndürün: dizi büyükten küçüğe sıralandığında, 1’den başlayarak sayılan k. sıradaki değer.

Eşit değerler ayrı ayrı sayılır. [5, 5, 1] içinde en büyük değer 5, ikinci en büyük değer de 5'tir.

Fonksiyon

findKthLargest(nums: integer-array, k: integer) → integer

numsinteger-array: sıralanacak değerler
kinteger: hangi en büyük değerin döndürüleceği, en büyük değer için 1
Döndürürinteger: yinelenenleri sayarak k. en büyük değer

Kısıtlar

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Eşit değerler ayrı değerler olarak sayılır.

Örnekler

Girdi: nums = [7, 2, 9, 4, 9, 1]k = 2
Çıktı: 9
Açıklama: Değerler büyükten küçüğe doğru 9, 9, 7, 4, 2, 1 şeklindedir. İki tane 9 ayrı ayrı sayılır, bu nedenle ikinci en büyük değer 7 değil, 9 olur.

Girdi: nums = [5, -3, 8, 0, 2]k = 4
Çıktı: 0
Açıklama: En büyükten en küçüğe değerler 8, 5, 2, 0, -3 şeklindedir ve bunların dördüncüsü 0 değeridir.

Girdi: nums = [6]k = 1
Çıktı: 6
Açıklama: Tek bir değer ve k = 1 ile, bu değer en büyüktür.

Gönderirken +15 gizli test

Ek soru

Değerler artık teker teker geliyor. Her yeni değer geldiğinde, o ana kadar görülen tüm değerlerin medyanını değer başına O(log n) sürede hesaplayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Sıralayıp bir konumu okumak soruyu yanıtlar ve burada yeterince hızlıdır. Bir mülakatçının görmek istediği, bu sıralamanın ne kadarını atlayabileceğinizdir; çünkü tüm n konumlarına değil, tek bir konuma ihtiyacınız var. k boyutunda bir min-yığın, yalnızca hâlâ yanıt olabilecek değerleri tutar; quickselect ise quicksort gibi bölümlere ayırır ama yalnızca yanıtı içeren tarafı izler ve böylece ortalama çalışma süresini O(n) düzeyine indirir.

Bir konumu sırala ve oku

Sezgi

k'ıncı en büyük değer, sıralı düzene göre tanımlanır; bu nedenle değerleri bu düzene göre sıralayın. Büyükten küçüğe sıralandığında [7, 2, 9, 4, 9, 1] dizisi [9, 9, 7, 4, 2, 1] olur ve k'ıncı en büyük değer k-1 indeksinde bulunur. k = 2 için bu, 1. indekstir; yani ikinci 9. Sıralama en küçük değeri başa koyuyorsa bunun yerine n-k indeksini okuyun: [1, 2, 4, 7, 9, 9] dizisinin 4. indeksindeki değer de aynı 9'dur.

Yinelenen değerler için özel bir işlem gerekmez: sıralama her kopyayı korur ve her kopya kendi konumunu alır.

n = 10^4 için sıralama yaklaşık n log n ≈ 1.3 × 10^5 karşılaştırma yapar ve tüm testleri geçer. Gereksiz olan, yalnızca tek bir konum önemliyken tüm n değeri sıralamasıdır. Sonraki iki yaklaşım bu işin daha azını yapar.

Algoritma

Çağıranın dizisi olduğu gibi kalsın diye nums öğesini kopyalayın.
Kopyayı sıralayın. Sayısal karşılaştırma kullanın; bazı diller varsayılan olarak sayıları metin olarak karşılaştırır.
Büyükten küçüğe sıralama için k-1 indeksini, küçükten büyüğe sıralama içinse n-k indeksini döndürün.

def findKthLargest(nums, k):
    # Largest first: the k-th largest sits at index k-1.
    ordered = sorted(nums, reverse=True)
    return ordered[k - 1]

En büyük k öğeyi bir min-yığında tutun

Sezgi

k'ıncı en büyük değer, en büyük k değerin en küçüğüdür. Bu yüzden nums dizisini bir kez dolaş ve şimdiye kadar görülen en büyük k değeri bir min-heap'te tut. Min-heap'in tepesinde en küçük değer bulunur; bu da tam olarak cevap adayıdır.

Bir x değeri geldiğinde ve heap'te k'dan az değer varsa, onu ekle. Aksi takdirde x'i tepeyle karşılaştır. x daha büyük değilse, tuttuğun en az k değer x kadar büyüktür; dolayısıyla x asla cevap olamaz ve onu atlayabilirsin. x daha büyükse, tepedeki değer en büyük k değerin dışına çıkmıştır: onu x ile değiştir. k = 4 olan 2. örnekte, ilk dört değer heap'i 5, -3, 8, 0 ile doldurur ve tepedeki değer -3'tür. Ardından 2, -3'ten büyük olduğu için onun yerine geçer; tepedeki değer 0 olur ve cevap 0'dır.

Her değer en fazla bir O(log k) heap işlemi gerektirir; bu nedenle toplam süre O(n log k), bellek kullanımı ise O(k)'dır. Bu, k küçük olduğunda sıralamadan daha verimlidir ve bir akış üzerinde çalışır: tüm değerleri aynı anda bellekte tutman gerekmez. Python'da heapq, Java'da PriorityQueue, C++'ta greater ile priority_queue, Go'da container/heap, Rust'ta Reverse ile BinaryHeap ve PHP'de SplMinHeap bulunur. Diğer dillerdeki kod, heap'i bir dizide kurar; burada i indeksindeki düğümün çocukları 2i+1 ve 2i+2 indekslerinde, Lua ve R'de ise 1'den sayıldığı için 2i ve 2i+1 indekslerinde bulunur.

Algoritma

Boş bir min-heap ile başlayın.
Her x değeri için, heap k değerinden daha az değer içeriyorsa onu ekleyin.
k değer içerdiğinde, yalnızca x en üstteki değerden büyükse en üstteki değeri x ile değiştirin.
Son değerden sonra heap'in en üstündeki değeri döndürün.

import heapq


def findKthLargest(nums, k):
    # A min-heap of the k largest values so far; its top is the smallest of them.
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x
    return heap[0]

Üç yönlü bölümlemeyle Quickselect

Sezgi

Quicksort bir pivot seçer ve diziyi bölümlere ayırır: daha küçük değerler soluna, daha büyük değerler sağına yerleşir. Bir bölümlemeden sonra pivot, her iki taraf henüz sıralanmamış olsa bile, sıralı dizideki son indeksine yerleşir. Quickselect bu olgudan yararlanır. Küçükten büyüğe sıralamada yanıt target = n-k indeksindedir. Bir bölümlemeden sonra target pivotun solunda, pivotun kendisinde veya sağında olabilir; bu nedenle bir tarafta devam eder, diğerini elersin.

[7, 2, 9, 4, 9, 1] ve k = 2 için target, 6-2 = 4 olur. 4 etrafında bölümle: 2 ve 1, 0 ve 1 indekslerini alır; 4, 2. indeksi alır; 7, 9, 9 ise 3 ile 5 arasındaki indeksleri alır. 4. indeks sağ tarafta olduğundan yalnızca 3 ile 5 arasındaki indeksleri tutarsın. Bunları 9 etrafında bölümle: 7, 3. indeksi alır ve iki 9 da 4. ve 5. indeksleri alır. 4. indeks 9 değerini tuttuğundan yanıt 9 olur.

Üç yönlü bölümleme kullan: pivotun altındaki değerler, ardından ona eşit değerler, sonra da üzerindeki değerler; bunları lt ve gt ile takip et. Eşit değerler bloğu [lt, gt] sıralı konumundadır; bu nedenle target bu bloğun içindeyse işlem tamamdır. Basit iki yönlü bölümlemeyle 10^4 tane 7 içeren bir dizi, her turda bir değer küçülür; bu yaklaşık 5 × 10^7 adım demektir. Üç yönlü sürüm ise bunu tek geçişte yanıtlar.

Pivotu rastgele seç. Pivot, aralığın orta yarısına yarı yarıya düşer; bu da aralığı en fazla dörtte üçüne indirir. Böylece beklenen iş, n değer üzerinde birkaç geçiştir: O(n). Her pivot uç değerlerden biri olursa en kötü durum yine O(n²) olur; ilk eleman gibi sabit bir seçim, girdi sıralı olduğunda bu duruma yol açar. Kod bir kopya üzerinde çalışır ve O(n) bellek kullanır; girdiyi değiştirebiliyorsan nums üzerinde doğrudan bölümleme yapmak bunu O(1) düzeyine indirir.

Algoritma

nums'u a'ya kopyala, target = n-k, lo = 0 ve hi = n-1 olarak ayarla.
a[lo..hi] içinden rastgele bir pivot seç.
a[lo..hi] dizisini pivotun altındaki, ona eşit ve üzerindeki değerlere göre böl; eşit değerleri a[lt..gt] aralığında bırak.
target < lt ise hi = lt-1 olarak ayarla; target > gt ise lo = gt+1 olarak ayarla; aksi hâlde pivotu döndür.
2. adımdan itibaren tekrarla.

import random


def findKthLargest(nums, k):
    a = list(nums)
    target = len(a) - k  # the answer's index once a is sorted smallest first
    lo, hi = 0, len(a) - 1
    while True:
        pivot = a[random.randint(lo, hi)]
        # Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        # Now a[lt..gt] all equal pivot, and they are in their sorted places.
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return pivot

Tuzaklar ve uç durumlar

Yanlış cevapların çoğu, tekrar eden öğelerden ve konumları saymanın iki yolunun karıştırılmasından kaynaklanır.

Önce tekrar eden öğeleri kaldırmak. Problem her kopyayı sayar: [7, 2, 9, 4, 9, 1] içinde k = 2 için cevap 9'dur; ancak diziyi bir kümeye dönüştürdükten sonra cevap 7 olur.
Yanlış indeksi okumak. k saymaya 1'den başlar; bu nedenle cevap, büyükten küçüğe sıralı dizide k-1 indeksinde, küçükten büyüğe sıralı dizide ise n-k indeksindedir; n-k-1 değil.
Sayıları metin olarak sıralamak. JavaScript ve TypeScript'te [10, 9, 2].sort(), [10, 2, 9] sonucunu verir. (a, b) => a - b iletin.
k boyutunda bir maksimum yığın kullanmak. En büyük öğeyi çıkarmak, k en küçük değeri tutar ve k'ıncı en küçük değeri döndürür.
İki yönlü bölümlendirme veya sabit bir pivot ile Quickselect kullanmak. Çok sayıda eşit değer ya da sıralanmış bir dizi, büyük testlerde de yer alan O(n²) maliyetine yol açar.

Sıkça sorulan sorular4

Dizideki K. En Büyük Elemanın zaman karmaşıklığı nedir?

Sıralama O(n log n) zaman alır. Boyutu k olan bir min-yığın O(n log k) zaman ve O(k) bellek gerektirir. Rastgele bir pivot kullanan Quickselect, ortalama olarak O(n) zaman alır; en kötü durumdaki O(n²) karmaşıklığına ise rastgele pivot nedeniyle rastlamak çok düşük bir olasılıktır.

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

Yığın, şimdiye kadar görülen en büyük k değeri saklar ve karşılaştırıp çıkarmanız gereken değer bunların en küçüğüdür. Bir min-heap bu değeri en üstte tutar. Bir max-heap yalnızca tüm n değerleri içine koyup k-1 kez pop ederseniz işe yarar; bu da O(n) bellek gerektirir.

k'ncı en büyük eleman için yığın mı yoksa quickselect mi kullanmalıyım?

Quickselect ortalama olarak daha hızlıdır: O(n); ancak tüm değerlerin bellekte bulunmasını gerektirir ve onları yeniden sıralar. Heap, kötü bir en kötü durum olmaksızın O(n log k) karmaşıklığındadır ve değerler teker teker geldiğinde ve hepsini saklayamadığınızda işe yarar. Bir mülakatta ikisini de açıklayın ve takip sorusunda isteneni kodlayın.

k'ıncı en büyük eleman en kötü durumda doğrusal zamanda bulunabilir mi?

Evet. Medyanların medyanı kuralı, değerlerin sabit bir oranını eleyeceği garanti edilen bir pivot seçer; bu da en kötü durumda seçimi O(n) yapar, ancak pratikte rastgele bir pivottan daha yavaştır. Değerler -10^4 ile 10^4 aralığıyla sınırlıysa, her değerin kaç kez geçtiğini sayabilir ve k değeri geçene kadar 10^4’ten aşağı doğru ilerleyebilirsiniz; bunun zaman karmaşıklığı O(n + 2 × 10^4) olur.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [7, 2, 9, 4, 9, 1]
k = 2

Beklenen

Kth Largest Element in an Array

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Bir konumu sırala ve oku

En büyük k öğeyi bir min-yığında tutun

Üç yönlü bölümlemeyle Quickselect

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler