Merge k Sorted Lists

Q: Jaka jest złożoność czasowa łączenia k posortowanych list?

W przypadku kopca minimalnego złożoność wynosi O(N log k) , gdzie N to łączna liczba wartości, a k to liczba list. Każda wartość jest raz dodawana i raz usuwana, a kopiec przechowuje najwyżej k elementów, więc każda operacja kosztuje O(log k) . Dodatkowe zużycie pamięci wynosi O(k) , nie licząc wyniku.

Q: Dlaczego nie umieścić wszystkich wartości razem i ich nie posortować?

To poprawne i zajmuje O(N log N) czasu, co jest w porządku dla małych danych wejściowych. Pomija fakt, że listy są już posortowane, więc dla każdej wartości ponosi koszt log N , podczas gdy kopiec ponosi koszt log k , a ponadto wymaga przechowywania wszystkich wartości jednocześnie w pamięci. Kopiec może również scalać listy napływające jako strumienie, czego sortowanie nie potrafi.

TrudneKopiec Lista wiązana

+10

Otrzymujesz k list liczb całkowitych jako wiersze lists. Każdy wiersz jest posortowany w kolejności niemalejącej, wiersze mogą mieć różne długości, a żaden wiersz nie jest pusty.

Scal je w jedną listę zawierającą wszystkie wartości ze wszystkich wierszy, posortowaną w kolejności niemalejącej, i zwróć ją. Wartość występująca kilka razy, w jednym wierszu lub w kilku, pojawia się w wyniku tyle samo razy.

Funkcja

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

listsinteger-2d-array: posortowane listy, po jednej w każdym wierszu, o możliwie różnej długości
Zwracainteger-array: każda wartość z każdego wiersza, na jednej posortowanej liście

Ograniczenia

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, a wszystkie wiersze łącznie zawierają co najwyżej 10⁴ wartości
-10⁴ ≤ lists[i][j] ≤ 10⁴
Każdy wiersz jest posortowany w kolejności niemalejącej.

Przykłady

Wejście: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Wyjście: [1, 2, 3, 4, 5, 6, 9, 10]
Wyjaśnienie: Najmniejsza wartość w całej tablicy to 1 — pierwsza wartość w drugim wierszu. Po niej wiersze zaczynają się od 2, 4 i 3, więc następna jest 2 i tak dalej. W trzecim wierszu wartości kończą się na 5, więc na końcu pozostają 6, 9 i 10.

Wejście: lists = [[5], [-2, 5, 7], [0, 5]]
Wyjście: [-2, 0, 5, 5, 5, 7]
Wyjaśnienie: Trzy piątki pochodzą z trzech różnych wierszy i wszystkie trzy pozostają. Liczba ujemna -2 jest sortowana przed 0.

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Znajdź najmniejszy zakres [a, b], który zawiera co najmniej jedną wartość z każdego wiersza. Czy ta sama sterta głów wierszy, wraz z największą dotąd głową, może znaleźć go w czasie O(N log k)?

Rozwiązanie

Każdy wiersz jest posortowany, więc najmniejsza wartość, której jeszcze nikt nie użył, zawsze jest pierwszą nieużytą wartością w którymś wierszu. Cały problem sprowadza się do znalezienia najmniejszej z k wartości na początku wierszy, N razy, gdzie N to liczba wartości. Sprawdzenie wszystkich wartości na początku wierszy wymaga k kroków dla każdej wartości. Kopiec minimum utrzymuje te wartości w odpowiedniej kolejności i udostępnia najmniejszą w O(log k), co zmniejsza łączną złożoność z O(N·k) do O(N log k). W klasycznej wersji każda lista jest listą wiązaną; tutaj każdy wiersz jest tablicą, a indeks dla każdego wiersza pełni rolę wskaźnika na węzeł.

Porównaj wszystkie k głów dla każdej wartości

Poprawne, ale nie kończy się na największych testach

Intuicja

Przechowuj jeden indeks dla każdego wiersza, pos[r], wskazujący pierwszą niewykorzystaną jeszcze wartość wiersza r: jego początek. Najmniejsza niewykorzystana wartość ze wszystkich musi być jednym z tych początków. W wierszu r każda niewykorzystana wartość znajduje się na pozycji pos[r] lub dalej, a wiersz jest posortowany, więc żadna z nich nie jest mniejsza od jego początku.

Znajdź więc najmniejszy początek, sprawdzając każdy wiersz, w którym są jeszcze wartości, dopisz go i przesuń indeks tego wiersza o jedną pozycję. Powtarzaj, aż wszystkie N wartości zostaną pobrane. To etap scalania w sortowaniu przez scalanie, rozszerzony z dwóch list do k.

W pierwszym przykładzie początki to na początku 2, 1 i 3, więc jako pierwsza zostaje pobrana 1, a początek drugiego wiersza zmienia się na 4. Następnie 2 (początki 2, 4, 3), potem 3 (początki 6, 4, 3), następnie 4, a potem 5, przez co trzeci wiersz zostaje opróżniony. W ostatnich trzech rundach porównywane są tylko 6 i 10, potem 9 i 10, a następnie samo 10.

Koszt to k porównań dla każdej z N wartości. Przy 10^4 wierszach zawierających po jednej wartości daje to 10^8 porównań. C, Java lub JavaScript wykonają je w czasie poniżej sekundy, ale Python potrzebuje ponad dziesięciu sekund, a podwojenie zarówno N, jak i k sprawia, że każdy język działa cztery razy wolniej. Marnotrawstwo widać w śladzie wykonania: po każdym wyborze zmienia się tylko jeden początek, a jednak w następnej rundzie ponownie odczytywanych jest wszystkich k początków.

Algorytm

Ustaw pos[r] = 0 dla każdego wiersza i policz wartości, N.
Powtórz N razy: sprawdź każdy wiersz, w którym pos[r] nadal mieści się w jego obrębie, i zapamiętaj wiersz, którego pierwszy element jest najmniejszy.
Dodaj ten pierwszy element do wyniku i zwiększ pos tego wiersza o 1.
Zwróć wynik.

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

Min-kopiec z k głowami

Intuicja

Skan ponownie odczytuje k pierwszych wartości, aby znaleźć najmniejszą, chociaż od ostatniej rundy zmieniła się tylko jedna z nich. Kopiec minimalny jest stworzony właśnie do tego: przechowuje zbiór liczb, z najmniejszą na wierzchu, a zarówno pobranie wartości ze szczytu, jak i dodanie liczby kosztuje O(log size).

Umieść w kopcu pierwszą wartość z każdego wiersza, oznaczoną numerem tego wiersza. Następnie powtarzaj: usuń najmniejszą parę (value, row), dopisz value, a jeśli w tym wierszu jest kolejna wartość, dodaj ją z tym samym oznaczeniem. W kopcu zawsze znajduje się dokładnie jeden wpis dla każdego wiersza, w którym pozostały jeszcze wartości — jego pierwsza wartość — więc na wierzchu znajduje się najmniejsza niewykorzystana wartość spośród wszystkich wierszy. To ta sama zasada co przy skanowaniu, tylko zastosowana szybciej.

Prześledźmy pierwszy przykład, numerując wiersze od 0. Na początku w kopcu znajdują się 2 (wiersz 0), 1 (wiersz 1) i 3 (wiersz 2). Usuń 1 i dodaj kolejną wartość z wiersza 1: 4. Usuń 2 i dodaj 6 z wiersza 0. Usuń 3 i dodaj 5 z wiersza 2. Usuń 4 i dodaj 10. Usuń 5: wiersz 2 został już w całości wykorzystany, więc niczego nie dodajemy, a w kopcu pozostają 6 i 10. Usuń 6 i dodaj 9. Usuń 9, a potem 10. Wynik to [1, 2, 3, 4, 5, 6, 9, 10].

Każda wartość trafia do kopca raz i raz go opuszcza, a kopiec nigdy nie przechowuje więcej niż k wpisów, więc każda z tych 2N operacji kosztuje O(log k). Dla N = k = 10^4 daje to około 2 × 10^4 × 14, czyli mniej niż 3 × 10^5 kroków, w porównaniu z 10^8 przy skanowaniu. Kopiec zajmuje O(k) pamięci, nigdy O(N), ponieważ przechowuje pierwszą wartość z każdego wiersza, a nie pozostałe wartości za nią.

W kilku wersjach kopiec jest tworzony ręcznie w tablicy numerów wierszy uporządkowanych według ich pierwszych wartości; dzieci elementu o indeksie i mają indeksy 2i+1 i 2i+2 (w Lua i R, gdzie indeksowanie zaczyna się od 1, są to 2i i 2i+1). Pozwala to też zaoszczędzić pracę: po pobraniu pierwszej wartości z wiersza kolejna wartość z tego wiersza nie jest mniejsza, więc wiersz pozostaje na szczycie i wystarczy raz przesunąć go w dół, zamiast usuwać go z kopca, a następnie ponownie dodawać.

Algorytm

Umieść (lists[r][0], r) dla każdego wiersza r w kopcu minimalnym uporządkowanym według wartości.
Gdy kopiec nie jest pusty, zdejmij najmniejszą parę (value, r) i dodaj value do wyniku.
Jeśli wiersz r ma następną wartość, umieść ją w kopcu razem z r.
Zwróć wynik, gdy kopiec będzie pusty.

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

Pułapki i przypadki brzegowe

Logika kopca jest krótka. Większość błędów wynika z tego, co trafia do kopca i w jakiej kolejności są w nim elementy.

Zapominanie, skąd pochodzi dana wartość. Jeśli kopiec przechowuje same wartości, po zdjęciu elementu nie da się ustalić, który wiersz należy przesunąć dalej. Przechowuj wiersz razem z wartością.
Przypadkowe użycie kopca maksymalnego. C++ priority_queue i Rust BinaryHeap umieszczają największy element na górze; użyj greater<> lub Reverse. Java PriorityQueue i Python heapq domyślnie zwracają najmniejszy element.
Remisy w Pythonowym heapq. Gdy dwie wartości są równe, porównanie krotek przechodzi do drugiego elementu. Numer wiersza można porównać bez problemu, ale węzła listy wiązanej już nie, a klasyczna wersja zawiesza się przy równych wartościach. Umieść jako drugi element numer wiersza lub licznik.
Wstawianie wszystkich wartości na początku. Sortowanie nadal będzie poprawne, ale kopiec urośnie do N elementów, a złożoność pracy wyniesie O(N log N). Zachowuj po jednym pierwszym elemencie z każdego wiersza.
Odczyt poza końcem krótkiego wiersza. Wiersze mają różne długości, więc przed wstawieniem kolejnej wartości sprawdź, czy wiersz ją zawiera.
Usuwanie duplikatów. Równe wartości z różnych wierszy są osobnymi wartościami i każda z nich powinna znaleźć się w wyniku.

Najczęstsze pytania4

Jaka jest złożoność czasowa łączenia k posortowanych list?

W przypadku kopca minimalnego złożoność wynosi O(N log k), gdzie N to łączna liczba wartości, a k to liczba list. Każda wartość jest raz dodawana i raz usuwana, a kopiec przechowuje najwyżej k elementów, więc każda operacja kosztuje O(log k). Dodatkowe zużycie pamięci wynosi O(k), nie licząc wyniku.

Dlaczego nie umieścić wszystkich wartości razem i ich nie posortować?

To poprawne i zajmuje O(N log N) czasu, co jest w porządku dla małych danych wejściowych. Pomija fakt, że listy są już posortowane, więc dla każdej wartości ponosi koszt log N, podczas gdy kopiec ponosi koszt log k, a ponadto wymaga przechowywania wszystkich wartości jednocześnie w pamięci. Kopiec może również scalać listy napływające jako strumienie, czego sortowanie nie potrafi.

Czy potrafisz połączyć k posortowanych list bez użycia kopca?

Tak, metodą dziel i zwyciężaj. Scalaj listy parami za pomocą scalania dwóch list, a następnie scalaj wyniki parami i tak dalej. Są log k rundy, a w każdej z nich każda wartość jest przetwarzana raz, więc złożoność również wynosi O(N log k). Scalanie list jedna po drugiej do rosnącego wyniku jest wolniejsze: wczesne wartości są kopiowane ponownie przy każdym scalaniu, co daje łącznie O(N·k).

Dlaczego sterta potrzebuje tylko początku każdej listy?

Każda lista jest posortowana, więc jej pierwsza niewykorzystana wartość jest najmniejszą z pozostałych. Najmniejsza wartość spośród wszystkich list jest zatem najmniejszą z ich pierwszych elementów, a żadna wartość znajdująca się głębiej na liście nie może być mniejsza. Gdy pierwszy element zostaje usunięty, następna wartość z tej samej listy staje się jej pierwszym elementem i zajmuje jego miejsce w kopcu.

Python

def mergeKLists(lists):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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