Merge k Sorted Lists

Q: Merge k Sorted Lists'in zaman karmaşıklığı nedir?

Bir min-heap ile karmaşıklık O(N log k) olur; burada N toplam değer sayısı, k ise liste sayısıdır. Her değer bir kez eklenip çıkarılır ve heap en fazla k girdi tutar. Çıktı dışında gereken ek bellek O(k) olur.

Q: Neden tüm değerleri bir araya getirip sıralamıyoruz?

Bu doğru ve O(N log N) zaman alır. Listelerin zaten sıralanmış olduğunu göz ardı eder; bu nedenle yığın log k maliyeti öderken her değer için log N maliyet öder ve tüm değerlerin aynı anda bellekte bulunmasını gerektirir. Yığın, akışlar hâlinde gelen listeleri de birleştirebilir.

ZorYığın (heap)Bağlı liste

+10

lists satırları olarak k adet tam sayı listesi alırsınız. Her satır azalmayan sırada sıralıdır, satırların uzunlukları farklı olabilir ve hiçbir satır boş değildir.

Bunları, her satırdaki tüm değerleri azalmayan sırada içeren tek bir listede birleştirin ve bu listeyi döndürün. Bir satırda veya birkaç satırda birden çok kez görünen bir değer, sonuçta da o kadar kez yer alır.

Fonksiyon

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: muhtemelen farklı uzunluklardaki sıralanmış listeler, her satırda bir tane
Döndürürinteger-array: her satırdaki her değeri tek bir sıralı listede

Kısıtlar

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length ve tüm satırlarda toplamda en fazla 10⁴ değer bulunur
-10⁴ ≤ lists[i][j] ≤ 10⁴
Her satır azalmayan sırada sıralanmıştır.

Örnekler

Girdi: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Çıktı: [1, 2, 3, 4, 5, 6, 9, 10]
Açıklama: Satırlar 2, 1 ve 3 ile başlıyor, bu yüzden önce 1 gelir. Sonra başlar 2, 4 ve 3 olur; bu yüzden 2 onu izler ve böyle devam eder. Üçüncü satır 5'ten sonra tükenir, geriye 6, 9 ve 10 kalır.

Girdi: lists = [[5], [-2, 5, 7], [0, 5]]
Çıktı: [-2, 0, 5, 5, 5, 7]
Açıklama: Üç tane 5, üç farklı satırdan gelir ve üçü de kalır. Negatif -2, 0'dan önce sıralanır.

Ek soru

Her satırdan bir değer içeren en küçük aralığı [a, b] bulun. Satır başlarından oluşan bir yığın ve en büyük satır başı bunu O(N log k) sürede yapabilir mi?

Çözüm

Her satır sıralanmıştır; bu nedenle kullanılmamış en küçük değer, her zaman bir satırın kullanılmamış ilk değeri, yani başıdır. Tüm k başlıkları taramak, N değerin her biri için k adım gerektirir. Başlıklardan oluşan bir min-heap, en küçüğünü O(log k) sürede verir; böylece toplam maliyet O(N·k) değerinden O(N log k) değerine düşer.

Tüm değerler için k başlığını karşılaştırın

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

Sezgi

Her satırın başında bir pos[r] dizini tut. Her turda tüm başlıkları oku, en küçüğünü ekle ve o satırın dizinini ilerlet: bu, iki listeden k listeye genişletilmiş merge sort birleştirme adımıdır. İlk örnekte başlıklar 2, 1 ve 3 olarak başlar; bu yüzden 1 çıkar ve ikinci satırın başlığı 4 olur.

N değerinin her biri, k satırın tümü üzerinde bir tarama gerektirir. Her birinde tek bir değer bulunan 10^4 satırla bu, 10^8 satır kontrolü demektir.

Algoritma

Her satır için pos[r] = 0 değerini ayarlayın ve değerleri sayarak N'yi bulun.
N kez tekrarlayın: pos[r] değeri hâlâ o satırın içinde olan her satıra bakın ve başındaki değeri en küçük olan satırı aklınızda tutun.
Bu baştaki değeri sonuca ekleyin ve o satırın pos değerini 1 artırın.
Sonucu döndürün.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

k başlığından oluşan min-yığın

Sezgi

Her seçimden sonra yalnızca bir baş değişir, ancak tarama tüm k değerlerini yeniden okur. Bir min-yığın, en küçük değere sahip olanları üstte tutar. Her başı satırıyla etiketle; böylece (value, row) öğesini çıkardıktan sonra hangi satırın sonraki değerini ekleyeceğini bilirsin. Yığında, değerleri kalan her satır için her zaman bir öğe bulunur; bu nedenle en üstteki öğe kullanılmamış en küçük değerdir.

İlk örnekte yığın 2, 1 ve 3 ile başlar. 1'i çıkar, 4'ü ekle. 2'yi çıkar, 6'yı ekle. 3'ü çıkar, 5'i ekle. 4'ü çıkar, 10'u ekle. 5'i çıkar: üçüncü satır tükenmiştir, bu yüzden hiçbir şey eklenmez. 6'yı çıkar, 9'u ekle; ardından 9 ve 10'u çıkar.

Her değer yığına bir kez girer ve bir kez çıkar; yığında hiçbir zaman k öğeden fazla bulunmaz: O(log k) karmaşıklığında 2N işlem. N = k = 10^4 için bu, 3 × 10^5 adımdan azdır. Yığın O(k) bellek kullanır.

Algoritma

Her r satırı için (lists[r][0], r) çiftini değere göre sıralanmış bir minimum yığına ekle.
Yığın boş değilken, en küçük (value, r) çiftini çıkar ve value değerini sonuca ekle.
r satırında bir sonraki değer varsa, bu değeri r ile birlikte ekle.
Yığın boşaldığında sonucu döndür.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

Tuzaklar ve uç durumlar

Yalnızca değerleri eklemek. Bir değer çıkarıldıktan sonra hangi satırda ilerleyeceğini bilemezsin. Değeri satır bilgisiyle birlikte sakla.
Yanlışlıkla max-heap kullanmak. C++ priority_queue ve Rust BinaryHeap en büyük değeri en üste koyar; greater<> veya Reverse kullan.
Başlangıçta tüm değerleri eklemek. Sonuç yine sıralı olur, ancak yığın N girdiye kadar büyür ve işlem O(N log N) olur.
Kısa bir satırın sonunu geçerek okumak. İlk örnekte üçüncü satırda iki değer vardır; bu yüzden eklemeden önce sonraki bir değerin olup olmadığını kontrol et.
Yinelenen değerleri atmak. İkinci örnekteki üç tane 5 ayrı değerlerdir ve hepsi sonuca dahil edilmelidir.

Sıkça sorulan sorular3

Merge k Sorted Lists'in zaman karmaşıklığı nedir?

Bir min-heap ile karmaşıklık O(N log k) olur; burada N toplam değer sayısı, k ise liste sayısıdır. Her değer bir kez eklenip çıkarılır ve heap en fazla k girdi tutar. Çıktı dışında gereken ek bellek O(k) olur.

Neden tüm değerleri bir araya getirip sıralamıyoruz?

Bu doğru ve O(N log N) zaman alır. Listelerin zaten sıralanmış olduğunu göz ardı eder; bu nedenle yığın log k maliyeti öderken her değer için log N maliyet öder ve tüm değerlerin aynı anda bellekte bulunmasını gerektirir. Yığın, akışlar hâlinde gelen listeleri de birleştirebilir.

k sıralı listeyi bir yığın kullanmadan birleştirebilir misin?

Evet, böl ve fethet yöntemiyle. Listeleri ikişerli olarak iki listeyi birleştirme yöntemiyle birleştir, ardından sonuçları ikişerli olarak birleştir ve bu şekilde devam et: her turda her değere bir kez dokunan log k tur, yani O(N log k). Listeleri büyüyen bir sonuca art arda eklemek daha yavaştır, O(N·k), çünkü başlardaki değerler her birleştirmede yeniden kopyalanır.

def mergeKLists(lists):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

Beklenen Çıktı

[1, 2, 3, 4, 5, 6, 9, 10]