Merge Two Sorted Lists

Q: İki sıralı listeyi birleştirmenin zaman karmaşıklığı nedir?

Bu, O(L1 + L2) şeklindedir: her karşılaştırma bir düğümü yerleştirir ve hiçbir düğüm iki kez yerleştirilmez. Düğüm nesneleriyle birleştirme, yalnızca bağlantıları değiştirdiği için O(1) ek bellek gerektirir. Burada kullanılan dizilerde ise paylaşılan bağlantı dizisi O(L1 + L2) bellek kullanır.

KolayBağlı liste İki işaretçi

+10

Sana, her biri aynı uzunlukta iki dizide saklanan iki tek yönlü bağlı liste verilir. İlk listede i düğümü values1[i] değerini tutar ve next1[i] düğümüne bağlanır. İkinci liste de next2 ve values2 ile aynı şekilde çalışır. Her iki listede de -1 listeyi sonlandırır ve baş düğüm 0'dır. Düğümler liste sırasına göre saklanmaz; bu yüzden bağlantıları takip et.

Her liste, bağlantıları boyunca azalmayan sırada sıralanmıştır. İki listeyi tek bir sıralı listede birleştir ve değerlerini sırayla döndür.

Fonksiyon

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: ilk listedeki her düğümün bağlandığı düğümün indeksi veya son düğümü için -1
values1integer-array: ilk listedeki her düğümün tuttuğu değer
next2integer-array: ikinci listedeki her düğümün bağlantı verdiği düğümün indeksi veya son düğümü için -1
values2integer-array: İkinci listedeki her düğümün tuttuğu değer
Döndürürinteger-array: birleştirilmiş listenin değerleri, sırasıyla

Kısıtlar

1 ≤ L1 ≤ 2000; burada L1, next1 ve values1 uzunluğudur.
1 ≤ L2 ≤ 2000; burada L2, next2 ve values2 uzunluğudur.
-1000 ≤ values1[i], values2[j] ≤ 1000
next1 içindeki her girdi -1 veya ilk listenin bir düğüm indeksi, next2 içindeki her girdi ise -1 veya ikinci listenin bir düğüm indeksidir.
0 düğümünden başlayarak her liste, düğümlerinin her birini tam olarak bir kez ziyaret eder ve ardından -1 değerine ulaşır. Döngü yoktur.
Bağlantıları boyunca her liste azalmayan sırada sıralanmıştır.

Örnekler

Girdi: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Çıktı: [1, 2, 3, 4, 6, 7, 9]
Açıklama: Bağlantıları izleyerek ilk liste 0, 2, 1 düğümlerini ziyaret eder ve 1, 4, 6 değerlerini okur; ikinci liste 2, 3, 7, 9 değerlerini okur. Her seferinde öndeki küçük değeri almak 1, 2, 3, 4, 6, 7, 9 sonucunu verir.

Girdi: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Çıktı: [-3, 0, 0, 5]
Açıklama: İlk liste -3, 0, 5 değerlerini, ikincisi ise tek değer olan 0 değerini içerir. Her iki 0 da sonuçta kalır, böylece sonuçta dört değer bulunur.

Girdi: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Çıktı: [1, 2, 3, 8, 10]
Açıklama: İkinci liste 1, 2, 3 şeklindedir; bunların tümü, ilk listeyi başlatan 8'den küçüktür. Önce ikinci listenin tamamı, ardından 8, 10 gelir.

Ek soru

k sıralı listeyi, N toplam düğüm sayısı olmak üzere, O(N log k) zamanda birleştirebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Her iki liste de sıralıdır, bu nedenle geriye kalan en küçük değer her zaman listelerden birinin başındadır. İki başı karşılaştırın, küçük olanı sonuca bağlayın ve o listede bir adım ilerleyin. N = L1 + L2 değerin tümünü sıralamak da işe yarar, ancak bu sıralı olma durumunu göz ardı eder ve O(N log N) maliyetlidir.

Tüm değerleri tek bir diziye koy ve sırala

Sezgi

Birleştirilmiş liste, tüm N değerlerinin sıralanmış hâlidir; bu nedenle iki değer dizisini tek bir dizide toplayıp sıralayın. Dizilerdeki düğümlerin sırası önemli değildir, çünkü sıralama her değeri doğru yere yerleştirir. N ≤ 4000 için bu yeterince hızlıdır; ancak sıralama, birleştirme en fazla N-1 karşılaştırma gerektirirken O(N log N) karşılaştırma gerektirir ve hiçbir bağlantıya dokunmaz; bu problemde sınanan beceri de budur.

Algoritma

values1 ve values2 öğelerini tek bir diziye kopyala.
Diziyi azalmayan sırada sırala.
Diziyi döndür.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Sahte bir başın arkasına düğümleri ekle

Sezgi

Buradaki işaretçi bir düğüm indeksidir. Her iki listenin düğümlerini tek bir zincirde birleştirmek için onlara tek bir numaralandırma verin: 2. listenin j numaralı düğümü, bağlantıları da aynı şekilde kaydırılarak L1+j numaralı düğüm olur. L1+L2 numaralı bir sahte düğüm, sonucun önünde yer alır.

a ve b işaretçilerini her listenin kullanılmamış ilk düğümünde, tail işaretçisini ise birleştirilmiş zincirin sonunda tutun. Her adımda tail işaretçisini küçük olan ilk düğüme bağlayın ve bu işaretçiyi ve tail işaretçisini ilerletin. Listelerden biri bittiğinde diğerinin geri kalanı zaten sıralanmış ve bağlıdır; bu nedenle tek bir atama onu bağlar. İlk örnekte 2. liste, 3 ile 6 arasındaki düğümlere dönüşür. 0, 3, 6, 2, 1 düğümlerinden sonra 1. liste boştur ve link[tail] = 4 ataması 7, 9 düğümlerini bağlar.

Her düğüm en fazla bir kez bağlanır: O(N) zaman. Paylaşılan bağlantı dizisi O(N) bellek kullanır; düğüm nesneleri ise hiç bellek gerektirmez.

Algoritma

Bir bağlantı dizisi oluştur: önce next1, ardından -1 değerlerini olduğu gibi bırakarak L1 kadar kaydırılmış next2, sonra kukla L1+L2 için -1. Eşleşen değerleri oluştur.
a = 0, b = L1 ve tail değerlerini kuklaya ayarla.
a da b de -1 olmadığı sürece, tail değerini küçük olana bağla (eşitlik durumunda a), o işaretçiyi ilerlet ve tail değerini onun üzerine taşı.
tail değerini, -1 olmayan a ya da b değerine bağla.
link[dummy] değerinden -1 değerine kadar ilerle ve değerleri topla.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

Tuzaklar ve uç durumlar

Dizileri indeks sırasına göre birleştirmek. Düğümler karışık sırada saklandığından values1 tek başına sıralı değildir: ilk örnekte [1, 6, 4] şeklindedir. Yalnızca 0 düğümünden başlayarak ilerlenen yol sıralıdır.
Kalanları unutmak. Listelerden biri tükendiğinde döngü durur ve diğer listenin geri kalanını atmak en büyük değerlerin kaybolmasına neden olur: ilk örnekte 7, 9.
Yanlış işaretçiyi ya da her ikisini birden ilerletmek. Yalnızca düğümünü aldığın liste ilerler.
İki numaralandırmayı karıştırmak. 2. listenin 2 düğümü, 1. listenin 2 düğümü değildir. 2. listenin indeks ve bağlantılarına L1 ekle, -1 değerini olduğu gibi bırak.

Sıkça sorulan sorular3

İki sıralı listeyi birleştirmenin zaman karmaşıklığı nedir?

Bu, O(L1 + L2) şeklindedir: her karşılaştırma bir düğümü yerleştirir ve hiçbir düğüm iki kez yerleştirilmez. Düğüm nesneleriyle birleştirme, yalnızca bağlantıları değiştirdiği için O(1) ek bellek gerektirir. Burada kullanılan dizilerde ise paylaşılan bağlantı dizisi O(L1 + L2) bellek kullanır.

Bağlı listeleri birleştirirken neden kukla düğüm kullanılır?

Bu olmadan, sonucun ilk düğümü için ayrı kod gerekir; çünkü onu arkasına bağlayacak henüz bir kuyruk yoktur. Kukla düğüm bir yer tutucu baştır, bu nedenle ilk düğüm de diğerleriyle aynı şekilde bağlanır. Sonunda kukla düğümün next düğümünü döndürürsün ve yer tutucu ortadan kalkar.

İki sıralı listeyi özyinelemeli mi yoksa yinelemeli olarak mı birleştirmelisiniz?

Özyinelemeli sürüm kısadır: daha küçük baş düğüm, geri kalan her şeyin birleştirilmesine bağlanır. Ancak her düğüm için bir yığın çerçevesi kullanır; bu nedenle birkaç bin düğümden oluşan bir liste, bazı dillerde yığın taşmasına neden olabilir. Kuyruk işaretçisi kullanan yinelemeli döngü, aynı işi sabit yığın alanında yapar.

def mergeTwoLists(next1, values1, next2, values2):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

Beklenen Çıktı

[1, 2, 3, 4, 6, 7, 9]