Median of Two Sorted Arrays

Q: Jaka jest złożoność czasowa algorytmu Median of Two Sorted Arrays?

Wyszukiwanie binarne po cięciu zajmuje O(log(min(m, n))) czasu i O(1) pamięci, ponieważ każdy krok zmniejsza o połowę liczbę możliwych cięć w krótszej liście. Scalanie zajmuje O(m + n) : dla dwóch list po 3000 elementów to około 12 kroków zamiast 6000.

Q: Dlaczego wyszukiwanie binarne w krótszej tablicy?

Ponieważ j = half-i . Gdy i przechodzi przez krótszą listę, j mieści się w zakresie od 0 do długości dłuższej listy, więc każdy odczyt mieści się w zakresie albo wykracza poza koniec, który traktujesz jak nieskończoność.

TrudneWyszukiwanie binarne

+10

Otrzymujesz dwie listy liczb całkowitych, nums1 i nums2, każda posortowana rosnąco i zawierająca co najmniej jedną wartość. Zwróć medianę wszystkich ich wartości razem, jako tekst.

Przy nieparzystej łącznej liczbie elementów mediana jest środkową wartością, na przykład "4". Przy parzystej liczbie jest średnią dwóch środkowych wartości, na przykład "2.5" lub "-0.5". Zapisz liczbę całkowitą bez kropki dziesiętnej, a zero jako "0", nigdy "-0". Dąż do złożoności czasowej O(log(min(m, n))).

Funkcja

findMedianSortedArrays(nums1: integer-array, nums2: integer-array) → string

nums1integer-array: pierwsza lista, posortowana od najmniejszej do największej
nums2integer-array: druga lista, posortowana od najmniejszej do największej
Zwracastring: mediana wszystkich wartości, jako tekst, na przykład „4” lub „-2.5”

Ograniczenia

1 ≤ nums1.length, nums2.length ≤ 3000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
Obie listy są posortowane w kolejności niemalejącej, a wartości mogą się powtarzać.

Przykłady

Wejście: nums1 = [1, 4]nums2 = [2, 7, 9]
Wyjście: "4"
Wyjaśnienie: Razem wartości to 1, 2, 4, 7, 9. Pięć wartości ma jedną wartość środkową — trzecią, czyli 4.

Pytanie dodatkowe

Czy możesz użyć tego samego podziału, aby znaleźć k-tą najmniejszą wartość z dwóch list dla dowolnego k w czasie logarytmicznym?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Połączenie list daje medianę w czasie O(m + n), ale większość odczytywanych wartości nie może zmienić odpowiedzi. Mediana zależy tylko od miejsca, w którym przebiega podział na dolną i górną połowę, a położenie tego podziału wyznacza jedna liczba: ile wartości dolna połowa pobiera z krótszej listy. Wyszukiwanie binarne znajduje ją w O(log(min(m, n))) krokach.

Połącz dwie listy

Intuicja

Połącz listy tak jak w algorytmie sortowania przez scalanie, tworząc jedną posortowaną listę merged. Przy total = m + n dodaj merged[(total-1)/2] i merged[total/2], używając dzielenia całkowitego. Dla nieparzystej wartości total obie pozycje wskazują tę samą środkową wartość, a dla parzystej — dwie środkowe wartości, więc w obu przypadkach połowa ich sumy jest medianą.

Nawet jeśli zakończysz na środku, kroki scalania obejmują ponad połowę wartości, więc złożoność czasowa wynosi O(m + n).

Algorytm

Połącz listy w merged, zawsze wybierając mniejszą bieżącą wartość, a następnie dodaj pozostałą część listy, która została.
Dla total = m + n dodaj merged[(total-1)/2] i merged[total/2].
Zwróć połowę sumy jako tekst: podziel parzystą sumę przez 2; dla nieparzystej sumy zapisz znak, połowę wartości bezwzględnej i .5.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Merge the two sorted lists into one, the way merge sort does.
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])
    total = len(merged)
    # For an odd total both indexes point at the one middle value.
    return half_text(merged[(total - 1) // 2] + merged[total // 2])

Wyszukiwanie binarne na punkcie podziału

Intuicja

Niech dolna połowa zawiera half = (m+n+1)/2 wartości; gdy łączna liczba jest nieparzysta, dolna połowa zawiera tę dodatkową wartość. Pobiera ona i wartości z początku nums1 oraz j = half-i z początku nums2. Podział jest prawidłowy, gdy żadna wartość poniżej niego nie jest większa od żadnej wartości powyżej niego. Każda lista jest posortowana, więc pozostają dwa warunki: left1 ≤ right2 i left2 ≤ right1, gdzie left to ostatnia wartość z listy, która trafia do dolnej połowy, a right to pierwsza wartość, która pozostaje poza nią. Brakująca wartość po jednej ze stron oznacza minus lub plus nieskończoność.

Jeśli left1 > right2, i jest za duże; jeśli left2 > right1, jest za małe. Zatem i jest wyszukiwane binarnie w zakresie od 0 do m. Dla [1, 2] i [3, 4] i = 1 nie spełnia warunku, bo left2 = 3 > right1 = 2, a i = 2 go spełnia: (2 + 3) / 2 = 2.5.

Algorytm

Ustaw nums1 jako krótszą listę; niech half = (m+n+1)/2.
Przeprowadź wyszukiwanie binarne i od lo = 0 do hi = m, gdzie j = half-i.
Odczytaj left1 = nums1[i-1], right1 = nums1[i], left2 = nums2[j-1] i right2 = nums2[j], przyjmując nieskończoność poza końcem.
Jeśli left1 > right2, ustaw hi = i-1. Jeśli left2 > right1, ustaw lo = i+1.
W przeciwnym razie, dla nieparzystej łącznej liczby elementów zwróć max(left1, left2). Dla parzystej łącznej liczby elementów podziel max(left1, left2) + min(right1, right2) przez dwa.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Binary search over the shorter list.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2   # size of the left half; it gets the extra value when m + n is odd
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # values the left half takes from nums1
        j = half - i          # values it takes from nums2
        # An empty side counts as minus or plus infinity.
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
        if left1 > right2:
            hi = i - 1        # too many values from nums1
        elif left2 > right1:
            lo = i + 1        # too few values from nums1
        else:
            left_max = max(left1, left2)
            if (m + n) % 2 == 1:
                return str(left_max)
            return half_text(left_max + min(right1, right2))
    return ""  # not reached: sorted input always has a valid split

Pułapki i przypadki brzegowe

Dzielenie przez połowę z użyciem liczb zmiennoprzecinkowych. Python wypisuje medianę będącą liczbą całkowitą jako 3.0, a %f w C wypisuje 2.5 jako 2.500000. Zachowaj sumę jako liczbę całkowitą.
Zapisywanie ilorazu całkowitego i .5 dla nieparzystej sumy ujemnej. -1 / 2 daje 0 w C i Javie, więc dla -0.5 otrzymujemy 0.5; -5 // 2 daje -3 w Pythonie, więc dla -2.5 otrzymujemy -3.5. Podziel wartość bezwzględną przez 2, a potem przywróć znak.
Zapisywanie -0. Środkowe wartości -1 i 1 sumują się do 0, a odpowiedzią jest "0". Ustal znak na podstawie sumy.
Przeszukiwanie dłuższej tablicy. j = half-i może być mniejsze od 0 lub przekroczyć n. Najpierw zamień tablice miejscami.
Odczytywanie nums1[i-1], gdy i = 0, na przykład dla [9] i [1, 2]. Użyj nieskończoności dla brakujących wartości.

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu Median of Two Sorted Arrays?

Wyszukiwanie binarne po cięciu zajmuje O(log(min(m, n))) czasu i O(1) pamięci, ponieważ każdy krok zmniejsza o połowę liczbę możliwych cięć w krótszej liście. Scalanie zajmuje O(m + n): dla dwóch list po 3000 elementów to około 12 kroków zamiast 6000.

Dlaczego wyszukiwanie binarne w krótszej tablicy?

Ponieważ j = half-i. Gdy i przechodzi przez krótszą listę, j mieści się w zakresie od 0 do długości dłuższej listy, więc każdy odczyt mieści się w zakresie albo wykracza poza koniec, który traktujesz jak nieskończoność.

Jak zwrócić medianę bez użycia liczb zmiennoprzecinkowych?

Dodaj dwie środkowe wartości jako liczby całkowite. Podziel parzystą sumę przez 2. W przypadku nieparzystej sumy zapisz połowę jej wartości bezwzględnej i .5, a gdy suma jest ujemna, dodaj znak minus: -1 staje się "-0.5".

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

Test #1

Test #2

Test #3

Argumenty

nums1 = [1, 4]
nums2 = [2, 7, 9]

Oczekiwany wynik

"4"