Sort List

+10

Otrzymujesz jednokierunkową listę połączoną przechowywaną w dwóch tablicach o tej samej długości. Węzeł i przechowuje wartość values[i] i wskazuje na węzeł next[i], -1 oznacza koniec listy, a głową listy jest węzeł 0. Węzły nie są przechowywane w kolejności występowania na liście, a tablice mogą też zawierać pozostałe węzły, do których nie dociera przejście od węzła 0. Nie są one częścią listy, nawet jeśli ich wskaźniki prowadzą do niej.

Posortuj listę rosnąco według wartości i zwróć wartości jej węzłów w tej kolejności.

Funkcja

sortList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: indeks węzła, do którego prowadzi każdy węzeł, lub -1 dla ostatniego węzła
valuesinteger-array: wartość przechowywana przez każdy węzeł
Zwracainteger-array: wartości węzłów listy, od najmniejszej

Ograniczenia

1 ≤ n ≤ 4000, gdzie n jest długością next oraz values.
-1000 ≤ values[i] ≤ 1000
Każde next[i] ma wartość -1 lub jest indeksem węzła z zakresu od 0 do n-1.
Zaczynając od węzła 0, lista dociera do -1, nie odwiedzając żadnego węzła dwukrotnie.
Węzły, do których nie dociera przejście od węzła 0, nie są częścią listy. Ich wpisy next mogą wskazywać gdziekolwiek.

Przykłady

Wejście: next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
Wyjście: [1, 2, 3, 4, 5]
Wyjaśnienie: Przejście od węzła 0 odwiedza węzły 0, 3, 2, 4, 1, więc lista ma postać 4, 2, 3, 5, 1. Po posortowaniu otrzymujemy 1, 2, 3, 4, 5.

Wejście: next = [2, 0, -1, -1]values = [6, 9, -2, 5]
Wyjście: [-2, 6]
Wyjaśnienie: Lista to 0 → 2, co oznacza 6, -2. Węzły 1 i 3 nigdy nie są osiągane od głowy, więc ich wartości 9 i 5 są pomijane, mimo że węzeł 1 wskazuje na węzeł 0.

Wejście: next = [1, 2, 3, -1]values = [3, -1, 3, -1]
Wyjście: [-1, -1, 3, 3]
Wyjaśnienie: Lista zawiera 3, -1, 3, -1. Równe wartości pozostają w odpowiedzi tyle razy, ile występują: -1, -1, 3, 3.

Pytanie dodatkowe

Czy potrafisz posortować, ponownie łącząc węzły, w czasie O(n log n), bez kopiowania wartości?

Rozwiązanie

Quicksort i heapsort opierają się na dostępie swobodnym, a lista jednokierunkowa umożliwia poruszanie się tylko do przodu. Pasuje tu sortowanie przez scalanie: dzielenie listy w jej środku i scalanie dwóch posortowanych list polegają na przechodzeniu do przodu, więc sortuje ono same połączenia w czasie O(n log n). Tutaj n oznacza długość tablic.

Skopiuj wartości do tablicy i posortuj ją

Intuicja

Lista to wartości odwiedzane podczas przechodzenia node = next[node] od węzła 0 aż do -1. Zbierz te wartości w nowej tablicy, posortuj ją za pomocą wbudowanej metody sortowania i zwróć ją. Nie możesz bezpośrednio sortować values: w drugim przykładzie zawiera ona 9 i 5, których nie ma na liście.

Przejście zajmuje O(n), a sortowanie O(n log n), przy dodatkowej pamięci O(n). Sama lista nigdy nie jest modyfikowana, dlatego osoby prowadzące rozmowy kwalifikacyjne pytają o kolejne podejście.

Algorytm

Zacznij od pustej tablicy i node = 0.
Dopóki node nie jest równe -1, dodawaj values[node] i przechodź do next[node].
Posortuj tablicę rosnąco i zwróć ją.

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

Sortowanie przez scalanie list

Intuicja

Wolny wskaźnik, który przesuwa się o jedno ogniwo, i szybki wskaźnik, który przesuwa się o dwa, znajdują środek podczas jednego przejścia. Do połączenia dwóch posortowanych list wystarczą ich pierwsze węzły: wybierz mniejszy i przejdź dalej. Żaden z tych kroków nie wymaga drugiej tablicy.

W pierwszym przykładzie slow zatrzymuje się na 3, a przecięcie łącza dzieli 4, 2, 3, 5, 1 na 4, 2, 3 i 5, 1. Po posortowaniu otrzymujemy 2, 3, 4 i 1, 5, a scalanie pobiera kolejno 1, 2, 3, 4, a następnie dołącza pozostałe 5.

Na każdym poziomie dzielenia każdy węzeł jest przetwarzany stałą liczbę razy, a poziomów jest około log n, więc czas działania wynosi O(n log n). Jedyną dodatkową pamięcią jest stos rekurencji, który dla 4000 węzłów ma około 12 wywołań głębokości.

Algorytm

Jeśli lista ma jeden węzeł (next[head] == -1), zwróć head.
Ustaw slow = head i fast = next[head]; przesuwaj slow o jedno łącze, a fast o dwa, dopóki fast i next[fast] nie będą równe -1.
Ustaw second = next[slow] i odetnij listę, ustawiając next[slow] = -1.
Posortuj obie połowy rekurencyjnie. Scal je: dołącz mniejszy węzeł z przodu po tail, aż jedna połowa będzie pusta, a następnie dołącz resztę drugiej.
Przejdź od zwróconej głowy i zbierz wartości.

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Pułapki i przypadki brzegowe

Sortowanie całej tablicy values. W drugim przykładzie, który wprowadza 9 i 5, tych wartości nie ma na liście.
Rozpoczynanie od fast na głowie listy. Przy dwóch węzłach slow trafia wtedy na drugi węzeł, przecięcie pozostawia pustą drugą połowę, a rekurencja nigdy nie zmniejsza rozmiaru problemu.
Zapominanie o przecięciu next[slow] = -1. Pierwsza połowa przechodzi wtedy w drugą, a oba wywołania sortują nakładające się listy.
Odrzucanie reszty połowy, gdy skończy się druga połowa. Te węzły znikają z wyniku.
W Lua i R tablice zaczynają się od indeksu 1: zachowaj indeksy węzłów liczone od 0 i odczytuj next[node + 1]. Wersja w R kopiuje tablicę odsyłaczy tylko raz, więc używa dodatkowej pamięci O(n).

Najczęstsze pytania3

Jaki jest najlepszy sposób na posortowanie listy wiązanej?

Sortowanie przez scalanie. Podział w środku, sortowanie obu połówek i ich scalanie przebiegają od początku do końca listy — w jedynym kierunku obsługiwanym przez listę jednokierunkową. Działa w czasie O(n log n) i ponownie łączy istniejące węzły.

Dlaczego sortowanie przez scalanie jest preferowane w przypadku list wiązanych zamiast sortowania szybkiego?

Quicksort może podzielić listę przez ponowne łączenie jej elementów, ale dobry element osiowy wymaga dostępu swobodnego, a wybranie głowy jako elementu osiowego sprawia, że posortowanie listy kosztuje O(n²). Merge sort zawsze dzieli listę na połowy, więc zachowuje złożoność O(n log n) dla dowolnych danych wejściowych.

Czy potrafisz posortować listę powiązaną w czasie O(n log n) i przy użyciu O(1) pamięci?

Tak, za pomocą sortowania przez scalanie oddolnego. Scala sąsiednie serie o długości 1, potem 2, a następnie 4, aż jedna seria obejmie całą listę. Wykonuje log n liniowych przebiegów, a jedyne używane miejsce w pamięci zajmuje kilka indeksów węzłów.

def sortList(next, values):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

next = [3, -1, 4, 2, 1]
values = [4, 1, 3, 2, 5]

Oczekiwany wynik

[1, 2, 3, 4, 5]