Merge Two Sorted Lists

Q: Jaka jest złożoność czasowa scalania dwóch posortowanych list?

To O(L1 + L2) : każde porównanie umieszcza jeden węzeł, a żaden węzeł nie jest umieszczany dwukrotnie. W przypadku obiektów węzłów scalanie wymaga O(1) dodatkowej pamięci, ponieważ zmienia tylko łącza. W przypadku użytych tutaj tablic współdzielona tablica łączy wymaga O(L1 + L2) pamięci.

ŁatweLista wiązana Dwa wskaźniki

+10

Otrzymujesz dwie jednokierunkowe listy połączone, każdą zapisaną w dwóch tablicach o tej samej długości. Na pierwszej liście węzeł i przechowuje wartość values1[i] i wskazuje węzeł next1[i]. Druga lista działa tak samo, używając next2 i values2. W obu listach -1 oznacza koniec listy, a głową jest węzeł 0. Węzły nie są zapisane w kolejności, w jakiej występują na liście, więc podążaj za odnośnikami.

Każda lista jest posortowana w kolejności niemalejącej wzdłuż odnośników. Połącz je w jedną posortowaną listę i zwróć jej wartości w kolejności.

Funkcja

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

next1integer-array: indeks węzła, z którym łączy się każdy węzeł pierwszej listy, lub -1 dla jej ostatniego węzła
values1integer-array: wartość przechowywana w każdym węźle pierwszej listy
next2integer-array: indeks węzła, do którego odwołuje się każdy węzeł drugiej listy, lub -1 dla jej ostatniego węzła
values2integer-array: wartość przechowywana przez każdy węzeł drugiej listy
Zwracainteger-array: wartości scalonej listy, w kolejności

Ograniczenia

1 ≤ L1 ≤ 2000, gdzie L1 jest długością next1 i values1.
1 ≤ L2 ≤ 2000, gdzie L2 to długość next2 i values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
Każdy element next1 to -1 lub indeks węzła z pierwszej listy, a każdy element next2 to -1 lub indeks węzła z drugiej listy.
Rozpoczynając od węzła 0, każda lista odwiedza każdy ze swoich węzłów dokładnie raz, a następnie dociera do -1. Nie ma cyklu.
Wzdłuż swoich połączeń każda lista jest posortowana w kolejności nierosnącej.

Przykłady

Wejście: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Wyjście: [1, 2, 3, 4, 6, 7, 9]
Wyjaśnienie: Podążając za linkami, pierwsza lista odwiedza węzły 0, 2, 1 i odczytuje 1, 4, 6; druga odczytuje 2, 3, 7, 9. Za każdym razem wybierając mniejszy element z początku listy, otrzymujemy 1, 2, 3, 4, 6, 7, 9.

Wejście: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Wyjście: [-3, 0, 0, 5]
Wyjaśnienie: Pierwsza lista zawiera -3, 0, 5, a druga składa się z pojedynczej wartości 0. Obie wartości 0 pozostają w wyniku, więc ma on cztery wartości.

Wejście: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Wyjście: [1, 2, 3, 8, 10]
Wyjaśnienie: Druga lista zawiera 1, 2, 3, wszystkie mniejsze niż 8, które rozpoczyna pierwszą listę. Najpierw pojawia się cała druga lista, a potem 8, 10.

Pytanie dodatkowe

Czy potrafisz scalić k posortowanych list w czasie O(N log k), gdzie N to łączna liczba węzłów?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Obie listy są posortowane, więc najmniejsza pozostała wartość zawsze znajduje się na początku jednej z nich. Porównaj pierwsze elementy obu list, dołącz mniejszy z nich do wyniku i przejdź do następnego elementu tej listy. Posortowanie wszystkich N = L1 + L2 wartości również zadziała, ale nie wykorzystuje tego porządku i wymaga O(N log N).

Umieść każdą wartość w jednej tablicy i posortuj ją

Intuicja

Połączona lista jest posortowaną wersją wszystkich N wartości, więc skopiuj obie tablice wartości do jednej i ją posortuj. Kolejność węzłów w tablicach nie ma znaczenia, ponieważ sortowanie umieszcza każdą wartość na właściwym miejscu. Przy N ≤ 4000 jest to wystarczająco szybkie, ale sortowanie wymaga O(N log N) porównań, podczas gdy scalanie wymaga ich co najwyżej N-1, a ponadto sortowanie nigdy nie dotyka żadnego łącza — a właśnie tę umiejętność sprawdza to zadanie.

Algorytm

Skopiuj values1 i values2 do jednej tablicy.
Posortuj tablicę w kolejności niemalejącej.
Zwróć ją.

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

Połącz węzły za głową wartowniczą

Intuicja

Wskaźnik oznacza tu indeks węzła. Aby połączyć węzły obu list w jeden łańcuch, nadaj im wspólną numerację: węzeł j listy 2 staje się węzłem L1+j, a jego łącza przesuwają się o tę samą wartość. Węzeł wartowniczy o numerze L1+L2 znajduje się przed wynikiem.

Ustaw a i b na pierwszym niewykorzystanym węźle każdej listy, a tail na końcu scalonego łańcucha. W każdym kroku połącz tail z mniejszym z pierwszych elementów i przesuń ten wskaźnik oraz tail dalej. Gdy skończą się elementy jednej listy, pozostała część drugiej jest już posortowana i połączona, więc wystarczy jedno przypisanie, aby ją dołączyć. W pierwszym przykładzie lista 2 staje się węzłami od 3 do 6. Po węzłach 0, 3, 6, 2, 1 lista 1 jest pusta, a link[tail] = 4 dołącza 7, 9.

Każdy węzeł jest łączony najwyżej raz: czas O(N). Wspólna tablica łączy wymaga O(N) pamięci, podczas gdy obiekty węzłów nie wymagałyby jej wcale.

Algorytm

Utwórz jedną tablicę odsyłaczy: next1, następnie next2 przesunięte o L1 (pozostaw -1 bez zmian), a potem -1 dla elementu fikcyjnego L1+L2. Utwórz odpowiadającą jej tablicę wartości.
Ustaw a = 0, b = L1, a tail na elemencie fikcyjnym.
Gdy ani a, ani b nie są równe -1, połącz tail z mniejszym elementem (przy remisie wybierz a), przesuń ten wskaźnik i ustaw tail na tym elemencie.
Połącz tail z tym z a i b, który nie jest równy -1.
Przejdź od link[dummy] do -1 i zbierz wartości.

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

Pułapki i przypadki brzegowe

Łączenie tablic w kolejności indeksów. Węzły są przechowywane w losowej kolejności, więc sama tablica values1 nie jest posortowana: w pierwszym przykładzie ma postać [1, 6, 4]. Posortowane jest tylko przejście od węzła 0.
Zapominanie o pozostałych elementach. Gdy jedna lista się wyczerpie, pętla się zatrzymuje, a pominięcie reszty drugiej listy powoduje utratę największych wartości: 7, 9 w pierwszym przykładzie.
Przesuwanie niewłaściwego wskaźnika albo obu. Przesuwa się tylko ta lista, z której wzięto węzeł.
Mieszanie numeracji obu list. Węzeł 2 listy 2 to nie węzeł 2 listy 1. Przesuń indeksy i odsyłacze listy 2 o L1, a -1 pozostaw bez zmian.

Najczęstsze pytania3

Jaka jest złożoność czasowa scalania dwóch posortowanych list?

To O(L1 + L2): każde porównanie umieszcza jeden węzeł, a żaden węzeł nie jest umieszczany dwukrotnie. W przypadku obiektów węzłów scalanie wymaga O(1) dodatkowej pamięci, ponieważ zmienia tylko łącza. W przypadku użytych tutaj tablic współdzielona tablica łączy wymaga O(L1 + L2) pamięci.

Dlaczego podczas scalania list połączonych używać węzła wartowniczego?

Bez niego pierwszy węzeł wyniku wymaga osobnego kodu, ponieważ nie ma jeszcze ogona, za którym można go podłączyć. Węzeł zastępczy jest atrapą głowy, więc pierwszy węzeł jest podłączany tak samo jak każdy inny. Na końcu zwracasz następny węzeł atrapy, a węzeł zastępczy znika.

Czy połączyć dwie posortowane listy rekurencyjnie czy iteracyjnie?

Wersja rekurencyjna jest krótka: mniejsza głowa jest łączona z wynikiem scalania wszystkich pozostałych elementów. Jednak wykorzystuje jedną ramkę stosu na węzeł, więc lista składająca się z kilku tysięcy węzłów może spowodować przepełnienie stosu w niektórych językach. Iteracyjna pętla ze wskaźnikiem na ogon wykonuje tę samą pracę przy stałym wykorzystaniu miejsca na stosie.

def mergeTwoLists(next1, values1, next2, values2):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

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