Merge k Sorted Lists

Q: K Sıralı Listeyi Birleştirmenin zaman karmaşıklığı nedir?

Min-heap ile 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 giriş tutar; bu nedenle her işlem O(log k) maliyetlidir. Çıktı dışında ek bellek kullanımı O(k) olur.

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

Bu doğrudur ve O(N log N) zaman alır; küçük girdiler için uygundur. Listelerin zaten sıralı olduğu gerçeğini göz ardı eder; bu nedenle yığın log k maliyetine katlanırken her değer için log N maliyetine katlanır ve tüm değerlerin aynı anda bellekte bulunmasını gerektirir. Yığın, akışlar hâlinde gelen listeleri de birleştirebilir; sıralama bunu yapamaz.

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

+10

lists satırları olarak k adet tam sayı listesi alırsın. 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ştir ve bu listeyi döndür. 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: Uzunlukları farklı olabilecek, her satırda bir tane bulunan sıralı listeler
Döndürürinteger-array: her satırdaki tüm değerler, sıralanmış tek bir listede

Kısıtlar

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length ve tüm satırlar birlikte en fazla 10⁴ değer içerir
-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: Genel olarak en küçük değer, ikinci satırın ilk değeri olan 1'dir. Ondan sonra satırlar 2, 4 ve 3 ile başlar; bu nedenle sıradaki değer 2'dir ve böyle devam eder. Üçüncü satır 5'ten sonra biter ve sonunda 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.

Gönderirken +14 gizli test

Ek soru

Her satırdan en az bir değer içeren en küçük [a, b] aralığını bulun. Aynı satır başı yığını ve şimdiye kadarki en büyük satır başını kullanarak bunu O(N log k) sürede bulabilir misiniz?

Çözüm

Her satır sıralıdır; bu nedenle henüz kimsenin kullanmadığı en küçük değer, her zaman bir satırın kullanılmamış ilk değeridir. Problemin tamamı, N kez olmak üzere k satır başının en küçüğünü bulmaktır; burada N, değerlerin sayısıdır. Tüm başları taramak, her değer için k adım gerektirir. Bir min-yığın başları sıralı tutar ve 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. Klasik biçimde her liste bağlantılı bir listedir; burada ise her satır bir dizidir ve satır başına tutulan bir indeks, düğüm işaretçisinin görevini görür.

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

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

Sezgi

Her satır için, henüz kullanmadığınız ilk değeri, yani satırın başını gösteren bir indeks tutun: pos[r]. Kullanılmamış değerlerin en küçüğü mutlaka bu başlardan biridir. r satırında, kullanılmamış her değer pos[r] konumunda veya sonrasında bulunur ve satır sıralı olduğundan bunların hiçbiri baştan küçük değildir.

Bu nedenle, hâlâ değer içeren her satıra bakarak en küçük başı bulun, onu ekleyin ve o satırın indeksini bir adım ilerletin. N değerin tamamı çıkana kadar tekrarlayın. Bu, birleştirme sıralamasının birleştirme adımıdır; iki listeden k listeye genişletilmiştir.

İlk örnekte başlar başlangıçta 2, 1 ve 3'tür; bu nedenle önce 1 çıkar ve ikinci satırın başı 4 olur. Sonra 2 (başlar 2, 4, 3), ardından 3 (başlar 6, 4, 3), sonra 4 ve ardından üçüncü satırı boşaltan 5 gelir. Son üç turda yalnızca 6 ile 10, sonra 9 ile 10, ardından da yalnızca 10 karşılaştırılır.

Her N değer için maliyet k karşılaştırmadır. Her biri tek değer içeren 10^4 satır olduğunda bu, 10^8 karşılaştırma demektir. C, Java veya JavaScript bunu bir saniyeden kısa sürede tamamlar, ancak Python'ın on saniyeden fazlasına ihtiyacı vardır; hem N hem de k iki katına çıkarıldığında her dil dört kat yavaşlar. İzleme çıktısında israf açıkça görülür: her seçimden sonra yalnızca bir baş değişmiştir, ancak bir sonraki turda yine tüm k baş okunur.

Algoritma

Her satır için pos[r] = 0 ayarlayın ve değerleri sayarak N'yi bulun.
N kez tekrarlayın: pos[r] değeri hâlâ satırın içindeyken her satıra bakın ve başı en küçük olan satırı belirleyin.
Bu başı 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ığının min-heap’i

Sezgi

Tarama, en küçüğünü bulmak için k başı yeniden okur; oysa son turdan beri yalnızca bir baş değişmiştir. Min-yığın tam da bunun için oluşturulur: sayılardan oluşan bir kümenin en küçüğünü tepede tutar ve hem tepeyi alma hem de bir sayı ekleme işlemi O(log size) maliyetindedir.

Her satırın ilk değerini, satır numarasıyla etiketleyerek yığına koy. Ardından tekrarla: en küçük (value, row) çiftini çıkar, value değerini ekle ve o satırda başka bir değer varsa aynı etiketle yığına koy. Yığın, hâlâ değerleri olan her satır için tam olarak bir girdi, yani o satırın başını tutar; bu nedenle tepedeki değer, henüz kullanılmamış değerlerin tümü içindeki en küçüğüdür. Taramanın kuralı budur; yalnızca daha hızlı yanıtlanır.

Satırları 0'dan başlayarak numaralandırıp ilk örneği adım adım izle. Yığın başlangıçta 2 (satır 0), 1 (satır 1) ve 3 (satır 2) değerlerini içerir. 1'i çıkar ve satır 1'in sonraki değeri olan 4'ü ekle. 2'yi çıkar ve satır 0'dan 6'yı ekle. 3'ü çıkar ve satır 2'den 5'i ekle. 4'ü çıkar ve 10'u ekle. 5'i çıkar: satır 2'deki değerler tükenmiştir, dolayısıyla yığına hiçbir şey eklenmez ve yığında 6 ile 10 kalır. 6'yı çıkar ve 9'u ekle. Önce 9'u, ardından 10'u çıkar. Sonuç [1, 2, 3, 4, 5, 6, 9, 10] olur.

Her değer yığına bir kez girip bir kez çıkar ve yığın hiçbir zaman k girdiden fazlasını tutmaz; dolayısıyla bu 2N işlemin her biri O(log k) maliyetindedir. N = k = 10^4 olduğunda bu yaklaşık 2 × 10^4 × 14, yani taramadaki 10^8 adıma kıyasla 3 × 10^5'ten az adımdır. Yığın O(k) bellek kullanır, hiçbir zaman O(N) kullanmaz; çünkü arkasındaki değerleri değil, her satırın bir başını tutar.

Birkaç sürüm, yığını elle kurar: satır numaralarından oluşan bir dizide, her satırın başına göre sıralama yapar. i yuvasının çocukları 2i+1 ve 2i+2 yuvalarındadır (1'den başlayan sayım kullanan Lua ve R'de 2i ve 2i+1). Bu ayrıca işten tasarruf sağlar: tepedeki satırın başı alındıktan sonra satırın sonraki değeri daha küçük olmadığından, satır tepede kalır ve aşağı doğru yalnızca bir kez elenir; önce çıkarıp ardından eklemek gerekmez.

Algoritma

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

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

Yığın mantığı kısadır. Hataların çoğu, yığına ne konduğundan ve hangi sırayla düzenlendiğinden kaynaklanır.

Bir değerin nereden geldiğini unutmak. Yığın yalnızca değerleri tutuyorsa, bir çıkarma işleminden sonra hangi satırın ilerletileceğini bilemezsiniz. Değeri satır bilgisiyle birlikte saklayın.
Yanlışlıkla maksimum yığın kullanmak. C++ priority_queue ve Rust BinaryHeap en büyük değeri en üste koyar; greater<> veya Reverse kullanın. Java'nın PriorityQueue ve Python'un heapq yapıları en küçük değeri en üste koyar.
Python heapq içindeki eşit değerler. İki değer eşit olduğunda, demet karşılaştırması ikinci öğeye geçer. Bir satır numarası sorunsuz karşılaştırılır; ancak bağlı liste düğümü karşılaştırılamaz ve klasik sürüm eşit değerlerde çöker. İkinci öğe olarak bir satır numarası veya sayaç kullanın.
Başlangıçta her değeri eklemek. Sıralama yine doğru olur, ancak yığın N öğeye kadar büyür ve işlem O(N log N) olur. Her satırdan yalnızca bir başlık öğesini tutun.
Kısa bir satırın sonunu aşacak şekilde okumak. Satırların uzunlukları farklıdır; bu nedenle yeni bir değer eklemeden önce satırda sonraki bir değer olup olmadığını kontrol edin.
Yinelenen değerleri atmak. Farklı satırlardaki eşit değerler ayrı değerlerdir ve hepsi sonuçta yer almalıdır.

Sıkça sorulan sorular4

K Sıralı Listeyi Birleştirmenin zaman karmaşıklığı nedir?

Min-heap ile 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 giriş tutar; bu nedenle her işlem O(log k) maliyetlidir. Çıktı dışında ek bellek kullanımı O(k) olur.

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

Bu doğrudur ve O(N log N) zaman alır; küçük girdiler için uygundur. Listelerin zaten sıralı olduğu gerçeğini göz ardı eder; bu nedenle yığın log k maliyetine katlanırken her değer için log N maliyetine katlanır ve tüm değerlerin aynı anda bellekte bulunmasını gerektirir. Yığın, akışlar hâlinde gelen listeleri de birleştirebilir; sıralama bunu yapamaz.

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

Evet, böl ve yönet yaklaşımıyla. Listeleri ikili gruplar hâlinde iki listeyi birleştirme yöntemiyle birleştir, ardından sonuçları ikili gruplar hâlinde birleştir ve böyle devam et. log k tur vardır ve her turda her değere bir kez dokunulur; dolayısıyla bu yöntem de O(N log k) zaman alır. Listeleri büyüyen bir sonuca teker teker ekleyerek birleştirmek daha yavaştır: başlardaki değerler her birleştirmede yeniden kopyalanır ve bu da toplamda O(N·k) zaman alır.

Yığın neden her listenin yalnızca başına ihtiyaç duyar?

Her liste sıralıdır, bu nedenle kullanılmamış ilk değeri, geriye kalan en küçük değeridir. Dolayısıyla tüm listelerdeki en küçük değer, başlarındaki değerlerin en küçüğüdür ve hiçbir listenin daha aşağısındaki bir değer onu geçemez. Bir baş değer listeden çıkarıldığında, aynı listedeki bir sonraki değer o listenin başı olur ve yığındaki yerini alır.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

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