Merge k Sorted Lists

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

W przypadku kopca minimum złożoność wynosi O(N log k) , gdzie N to łączna liczba wartości, a k to liczba list. Każda wartość jest dodawana i usuwana z kopca raz, a kopiec zawiera najwyżej k elementów. 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 prawda i zajmuje czas O(N log N) . Nie uwzględnia tego, ż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 jednoczesnego przechowywania w pamięci wszystkich wartości. Kopiec może również scalać listy napływające jako strumienie.

TrudneKopiec Lista wiązana

+10

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

Połącz je w jedną listę zawierającą wszystkie wartości ze wszystkich wierszy, posortowaną w porządku niemalejącym, i zwróć ją. Wartość, która występuje kilka razy, w jednym lub kilku wierszach, występuje 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 potencjalnie różnych długościach
Zwracainteger-array: każda wartość z każdego wiersza, w 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 nierosną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: Wiersze zaczynają się od 2, 1 i 3, więc najpierw występuje 1. Głowy mają następnie wartości 2, 4 i 3, więc po nim występuje 2 i tak dalej. W trzecim wierszu kończą się liczby po 5, pozostawiając 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.

Pytanie dodatkowe

Znajdź najmniejszy przedział [a, b] zawierający wartość z każdego wiersza. Czy kopiec głów wierszy oraz największa głowa pozwolą to zrobić w czasie O(N log k)?

Rozwiązanie

Każdy wiersz jest posortowany, więc najmniejsza niewykorzystana wartość jest zawsze pierwszą niewykorzystaną wartością w którymś wierszu — jego początkiem. Przeskanowanie wszystkich k początków wymaga k kroków dla każdej z N wartości. Kopiec minimalny zawierający początki zwraca najmniejszą wartość w O(log k), co zmniejsza złożoność z O(N·k) do O(N log k).

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

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

Intuicja

Umieść indeks pos[r] na początku każdego wiersza. W każdej rundzie odczytywany jest pierwszy element z każdego wiersza, dopisywany jest najmniejszy z nich, a indeks tego wiersza przesuwa się o jeden: to krok scalania sortowania przez scalanie, rozszerzony z dwóch list do k list. W pierwszym przykładzie pierwsze elementy to 2, 1 i 3, więc jako pierwszy trafia na wyjście 1, a pierwszym elementem drugiego wiersza staje się 4.

Każda z N wartości wymaga przejścia przez wszystkie k wierszy. Przy 10^4 wierszach zawierających po jednej wartości daje to 10^8 sprawdzeń wierszy.

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 wskazuje pozycję wewnątrz niego, i zapamiętaj wiersz, którego pierwszy element jest najmniejszy.
Dołącz ten pierwszy element do wyniku i dodaj 1 do pos tego wiersza.
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

Kopiec minimalny z k głowami

Intuicja

Po każdym pobraniu zmienia się tylko jeden element, a mimo to skanowanie odczytuje ponownie wszystkie k. Kopiec minimalny utrzymuje elementy na czele wierszy, z najmniejszym na górze. Oznacz każdy element numerem jego wiersza, aby po zdjęciu (value, row) wiedzieć, jaką następną wartość z tego wiersza wstawić. W kopcu zawsze znajduje się po jednym elemencie z każdego wiersza, w którym pozostały wartości, więc jego wierzchołek jest najmniejszą niewykorzystaną wartością.

W pierwszym przykładzie kopiec zaczyna od 2, 1 i 3. Zdejmij 1, wstaw 4. Zdejmij 2, wstaw 6. Zdejmij 3, wstaw 5. Zdejmij 4, wstaw 10. Zdejmij 5: trzeci wiersz jest już wyczerpany, więc niczego nie wstawiamy. Zdejmij 6, wstaw 9, a następnie zdejmij 9 i 10.

Każda wartość jest dodawana i usuwana raz, a kopiec nigdy nie zawiera więcej niż k elementów: 2N operacji o złożoności O(log k). Dla N = k = 10^4 to mniej niż 3 × 10^5 kroków. Kopiec zajmuje O(k) pamięci.

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 kolejną 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

Wstawianie samych wartości. Po zdjęciu elementu ze szczytu nie można określić, 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 szczycie; użyj greater<> lub Reverse.
Wstawianie wszystkich wartości na początku. Wynik nadal będzie posortowany, ale kopiec urośnie do N wpisów, a złożoność pracy wzrośnie do O(N log N).
Odczyt poza końcem krótkiego wiersza. W pierwszym przykładzie trzeci wiersz ma dwie wartości, więc przed wstawieniem sprawdź, czy istnieje następna wartość.
Pomijanie duplikatów. Trzy wartości 5 w drugim przykładzie są osobnymi wartościami i wszystkie powinny znaleźć się w wyniku.

Najczęstsze pytania3

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

W przypadku kopca minimum złożoność wynosi O(N log k), gdzie N to łączna liczba wartości, a k to liczba list. Każda wartość jest dodawana i usuwana z kopca raz, a kopiec zawiera najwyżej k elementów. 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 prawda i zajmuje czas O(N log N). Nie uwzględnia tego, ż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 jednoczesnego przechowywania w pamięci wszystkich wartości. Kopiec może również scalać listy napływające jako strumienie.

Czy potrafisz scalić k posortowanych list bez użycia kopca?

Tak, metodą dziel i zwyciężaj. Scal listy parami, używając scalania dwóch list, a następnie scalaj wyniki parami i tak dalej: log k rund, z których każda obejmuje każdą wartość raz, więc O(N log k). Scalanie list jedna po drugiej do powiększającego się wyniku jest wolniejsze — O(N·k) — ponieważ wcześniejsze wartości są kopiowane ponownie przy każdym scalaniu.

def mergeKLists(lists):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

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