Merge Sorted Array

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

Przy użyciu dwóch wskaźników złożoność wynosi O(m + n) , gdzie m i n to długości obu tablic. W każdym kroku umieszczana jest jedna wartość i żadna wartość nie jest sprawdzana dwukrotnie. Łączenie i sortowanie ma natomiast złożoność O((m + n) log(m + n)) .

Q: Jak scalić dwie posortowane tablice w miejscu?

Gdy w pierwszej tablicy jest miejsce na obie tablice na jej końcu, wypełnij ją od tyłu. Porównaj największe pozostałe wartości obu tablic, wpisz większą z nich do ostatniego wolnego miejsca i przesuń się w lewo. Wpisywanie od tyłu nigdy nie nadpisze wartości pierwszej tablicy, która nie została jeszcze umieszczona, więc druga tablica nie jest potrzebna.

Q: Czy scalanie dwóch posortowanych tablic jest tym samym co etap scalania w sortowaniu przez scalanie?

Tak. Sortowanie przez scalanie dzieli tablicę na połowy, sortuje każdą z nich, a następnie łączy te dwie posortowane połowy dokładnie za pomocą tej pętli z dwoma wskaźnikami. Wybieranie wartości z lewej strony w przypadku remisu zachowuje pierwotną kolejność równych wartości, dzięki czemu sortowanie przez scalanie jest stabilne.

Q: Dlaczego nie połączyć tablic i wywołać sort?

Zwraca poprawną odpowiedź i w praktyce często działa szybko. Ignoruje jednak fakt, że dane wejściowe są już posortowane, i wiąże się z dodatkowym czynnikiem log . Na rozmowie kwalifikacyjnej oczekiwaną odpowiedzią jest scalanie z użyciem dwóch wskaźników, ponieważ pokazuje, że potrafisz wykorzystać otrzymaną kolejność.

ŁatweDwa wskaźniki Sortowanie

+10

Otrzymujesz dwie tablice liczb całkowitych: nums1 i nums2. Każda z nich jest już posortowana w kolejności niemalejącej. Zwróć jedną tablicę zawierającą wszystkie wartości z obu tablic, również w kolejności niemalejącej. Wartość występująca w obu tablicach pojawia się w wyniku tyle razy, ile łącznie występuje w tych tablicach.

Funkcja

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: pierwsza posortowana tablica
nums2integer-array: druga posortowana tablica
Zwracainteger-array: wszystkie wartości obu tablic w jednej posortowanej tablicy o długości nums1.length + nums2.length

Ograniczenia

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 i nums2 są posortowane w kolejności niemalejącej.

Przykłady

Wejście: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Wyjście: [1, 2, 3, 4, 9, 10]
Wyjaśnienie: Odczytuj dwa pierwsze elementy i zachowuj mniejszy: 1, potem 2 i 3 z nums2, następnie 4 i 9 z nums1, a na końcu 10. Wynik zawiera wszystkie sześć wartości.

Wejście: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Wyjście: [-5, 0, 0, 0, 6, 8]
Wyjaśnienie: 0 pojawia się dwa razy w nums1 i raz w nums2, więc wynik zawiera trzy zera. -5 jest mniejsze od wszystkich elementów w nums2 i występuje jako pierwsze.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz połączyć k posortowanych tablic zawierających łącznie N wartości w czasie O(N log k)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Połączenie tablic i ich posortowanie daje prawidłową odpowiedź, ale nie wykorzystuje faktu, że obie połowy są już posortowane. Najmniejsza z pozostałych wartości znajduje się zawsze na początku jednej z dwóch tablic. Zachowaj po jednym indeksie dla każdej tablicy, za każdym razem wybieraj mniejszą wartość z początku, a jedno przejście utworzy wynik. To etap scalania w sortowaniu przez scalanie.

Połącz i posortuj

Intuicja

Umieść każdą wartość z nums1 i każdą wartość z nums2 w jednej tablicy, a następnie ją posortuj. Wynik zawiera właściwe wartości, każdą tyle razy, ile występowała, we właściwej kolejności.

Dla [1, 4, 9] i [2, 3, 10] połączona tablica to [1, 4, 9, 2, 3, 10], a sortowanie daje [1, 2, 3, 4, 9, 10].

Przy m wartościach w nums1 i n w nums2 ogólne sortowanie ma koszt O((m + n) log(m + n)). Działa i jest wystarczająco szybkie przy tych ograniczeniach, ale nie wykorzystuje podanej kolejności sortowania. Kolejne podejście ją wykorzystuje i eliminuje czynnik logarytmiczny.

Algorytm

Utwórz tablicę z wartościami nums1, po których następują wartości nums2.
Posortuj ją w kolejności rosnącej.
Zwróć ją.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

Dwa wskaźniki, po jednym na każdą tablicę

Intuicja

Zachowuj indeks i w nums1 i j w nums2, oba zaczynające się od 0. Wszystko przed i i przed j znajduje się już w wyniku. Najmniejszą niewykorzystaną wartością jest nums1[i] lub nums2[j], ponieważ każda tablica jest posortowana, a jej pozostałe wartości mogą być tylko większe. Dopisz mniejszą z nich i przesuń odpowiedni indeks.

Dla [1, 4, 9] i [2, 3, 10]: 1 jest mniejsze od 2, następnie 2 jest mniejsze od 4, 3 jest mniejsze od 4, 4 jest mniejsze od 10, 9 jest mniejsze od 10. Teraz wszystkie elementy z nums1 zostały wykorzystane, więc pozostała część nums2, czyli [10], jest kopiowana bez zmian. Wynik to [1, 2, 3, 4, 9, 10].

Każdy krok zapisuje jedną wartość, więc pętla wykonuje się m + n razy: czas O(m + n). Tablica wynikowa to jedyna dodatkowa pamięć.

Algorytm

Ustaw i i j na 0 i utwórz pusty wynik.
Gdy w obu tablicach pozostają jeszcze wartości, porównaj nums1[i] z nums2[j].
Dołącz mniejszą wartość i przesuń jej indeks do przodu. W przypadku remisu wybierz nums1[i].
Gdy jedna tablica się skończy, dołącz pozostałe elementy drugiej.
Zwróć wynik.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

Pułapki i przypadki brzegowe

Większość błędów pojawia się w chwili, gdy kończą się elementy jednej tablicy, albo przy porównywaniu wartości.

Kończenie pętli, gdy tylko skończą się elementy jednej tablicy, i zapominanie o pozostałych elementach drugiej. W przypadku [1, 2, 3] i [4, 5, 6] pętla kończy się po 1, 2 i 3, a 4, 5, 6 nadal trzeba skopiować.
Odczytywanie nums1[i], gdy i osiągnęło już koniec. Przed porównaniem sprawdź oba indeksy.
Pomijanie duplikatów. [0, 0] i [0] łączą się w [0, 0, 0], a nie [0].
W JavaScript i TypeScript funkcja sort() bez komparatora sortuje liczby jak tekst, więc [-5, 10, 9] zostaje posortowane jako [-5, 10, 9]. Przekaż (a, b) => a - b.
W Lua i R tablice zaczynają się od 1, więc oba indeksy zaczynają się od 1, a warunki zakresu używają <=.

Najczęstsze pytania4

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

Przy użyciu dwóch wskaźników złożoność wynosi O(m + n), gdzie m i n to długości obu tablic. W każdym kroku umieszczana jest jedna wartość i żadna wartość nie jest sprawdzana dwukrotnie. Łączenie i sortowanie ma natomiast złożoność O((m + n) log(m + n)).

Jak scalić dwie posortowane tablice w miejscu?

Gdy w pierwszej tablicy jest miejsce na obie tablice na jej końcu, wypełnij ją od tyłu. Porównaj największe pozostałe wartości obu tablic, wpisz większą z nich do ostatniego wolnego miejsca i przesuń się w lewo. Wpisywanie od tyłu nigdy nie nadpisze wartości pierwszej tablicy, która nie została jeszcze umieszczona, więc druga tablica nie jest potrzebna.

Czy scalanie dwóch posortowanych tablic jest tym samym co etap scalania w sortowaniu przez scalanie?

Tak. Sortowanie przez scalanie dzieli tablicę na połowy, sortuje każdą z nich, a następnie łączy te dwie posortowane połowy dokładnie za pomocą tej pętli z dwoma wskaźnikami. Wybieranie wartości z lewej strony w przypadku remisu zachowuje pierwotną kolejność równych wartości, dzięki czemu sortowanie przez scalanie jest stabilne.

Dlaczego nie połączyć tablic i wywołać sort?

Zwraca poprawną odpowiedź i w praktyce często działa szybko. Ignoruje jednak fakt, że dane wejściowe są już posortowane, i wiąże się z dodatkowym czynnikiem log. Na rozmowie kwalifikacyjnej oczekiwaną odpowiedzią jest scalanie z użyciem dwóch wskaźników, ponieważ pokazuje, że potrafisz wykorzystać otrzymaną kolejność.

Python

def merge(nums1, nums2):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Oczekiwane

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