Find Minimum in Rotated Sorted Array

Q: Jaka jest złożoność czasowa znajdowania minimum w obróconej posortowanej tablicy?

Czas O(log n) i dodatkowa pamięć O(1) przy wyszukiwaniu binarnym. Każdy krok zachowuje połowę zakresu, więc lista 5000 elementów wymaga co najwyżej 13 porównań. Skanowanie w poszukiwaniu miejsca spadku ma złożoność O(n) : odczytuje każdy element, gdy minimum znajduje się na końcu.

Q: Dlaczego porównujemy nums[mid] z nums[hi], a nie z nums[lo]?

Ponieważ nums[hi] zawsze rozstrzyga, po której stronie znajduje się minimum, a nums[lo] tego nie robi. Jeśli nums[mid] > nums[hi] , wartości muszą znajdować się między mid a hi ; w przeciwnym razie nums[mid..hi] rośnie, a minimum znajduje się w mid lub przed nim. W przypadku nums[lo] wynik nums[mid] > nums[lo] pasuje zarówno do nieobróconej listy, w której minimum to nums[lo] , jak i do obróconej, w której znajduje się ono na prawo od mid .

Q: Jak ustalić, ile razy obrócono posortowaną tablicę?

Wykonaj to samo wyszukiwanie binarne i zwróć lo , indeks minimum, zamiast nums[lo] . Jeśli liczysz rotację jako przeniesienie ostatniego elementu na początek, ten indeks jest liczbą rotacji. Jeśli liczysz ją jako przeniesienie pierwszego elementu na koniec, tak jak w tym zadaniu, liczba wynosi (n - lo) mod n : w [11, 13, 15, 17, 2, 5, 9] minimum znajduje się pod indeksem 4, a 7 minus 4 daje 3 przeniesione wartości.

Q: Czy wyszukiwanie binarne działa, gdy tablica zawiera duplikaty?

Nie, nie pozostaje bez zmian. W [2, 2, 2, 0, 2] nums[mid] może być równe nums[hi] , a wtedy nie można wykluczyć żadnej ze stron. Zmniejszenie zakresu przez hi = hi - 1 w takim przypadku jest bezpieczne, ponieważ kopia nums[hi] pozostaje w zakresie pod indeksem mid , ale przeszukanie listy równych wartości z jedną mniejszą wartością ukrytą pośród nich kosztuje wtedy O(n) .

ŚrednieWyszukiwanie binarne

+10

Lista różnych liczb całkowitych została posortowana rosnąco, a następnie obrócona: pewna liczba elementów, być może zero, została przeniesiona z początku na koniec w tej samej kolejności. Na przykład obrót [2, 5, 9, 11, 13, 15, 17] o 3 daje [11, 13, 15, 17, 2, 5, 9]. Otrzymujesz obróconą listę nums. Zwróć jej najmniejszą wartość w czasie O(log n).

Funkcja

findMin(nums: integer-array) → integer

numsinteger-array: obrócona, posortowana lista różnych liczb całkowitych
Zwracainteger: najmniejsza wartość w nums

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Wszystkie wartości w nums są różne.
nums jest rosnącą listą obróconą o pewną wartość k, gdzie 0 ≤ k < nums.length; k = 0 oznacza, że lista nie jest obrócona.

Przykłady

Wejście: nums = [11, 13, 15, 17, 2, 5, 9]
Wyjście: 2
Wyjaśnienie: Wartości rosną od 11 do 17, a następnie spadają do 2, gdzie zaczyna się drugi przebieg. Wyszukiwanie widzi 17 > 9 pod indeksem 3, więc minimum znajduje się na prawo od niego; następnie 5 ≤ 9 i 2 ≤ 5 cofają hi, aż zakres obejmuje tylko indeks 4, pod którym znajduje się 2.

Wejście: nums = [4, 7, 10, 12]
Wyjście: 4
Wyjaśnienie: Ta lista została obrócona o 0, więc nadal jest posortowana, a jej minimum to pierwsza wartość. Każda środkowa wartość jest mniejsza lub równa ostatniej, więc hi przesuwa się w lewo, aż dotrze do indeksu 0, w którym znajduje się 4.

Wejście: nums = [30, -6, 0, 8, 19]
Wyjście: -6
Wyjaśnienie: Cztery wartości zostały przeniesione z początku na koniec, więc największa wartość, 30, znajduje się teraz na początku, a minimum, -6, na indeksie 1. Wyszukiwanie zawęża zakres do indeksów 0 i 1, stwierdza, że 30 > -6, i przesuwa lo na 1.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz zwrócić k-tą najmniejszą wartość z nums w czasie O(log n), nie sortując jej?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Obrócona posortowana lista składa się z dwóch rosnących ciągów: [11, 13, 15, 17], a następnie [2, 5, 9]. Minimum to pierwsza wartość drugiego ciągu, tuż za jedynym miejscem, w którym wartości maleją. Przejście przez listę pozwala znaleźć ten spadek w czasie O(n). Porównanie jednej wartości ze środka z ostatnią wartością zakresu informuje, po której stronie spadku znajduje się środek, więc wyszukiwanie binarne pozwala znaleźć go w czasie O(log n).

Idź, aż wartości spadną

Intuicja

Na posortowanej liście każda wartość jest większa od poprzedniej. Obrócenie listy zachowuje posortowanie obu ciągów i tworzy dokładnie jedno miejsce, w którym ta zasada nie jest spełniona: największa wartość, po której następuje najmniejsza. Przejdź więc listę od lewej do prawej i zwróć pierwszą wartość, która jest mniejsza od sąsiada po lewej. Jeśli nie ma takiej wartości, lista została obrócona o 0, a minimum to nums[0].

W [11, 13, 15, 17, 2, 5, 9] przejście mija 13, 15 i 17, z których każda jest większa od poprzedniej, i zatrzymuje się na indeksie 4, gdzie 2 jest mniejsze od 17. To już lepsze niż znalezienie minimum spośród wszystkich wartości, ponieważ kończy się przy spadku, ale spadek może znajdować się w dowolnym miejscu. Gdy obrót przesunął jeden element, jak w [2, 3, 4, 5, 6, 7, 8, 1], przejście odczytuje całą listę: 5000 porównań dla 5000 elementów, podczas gdy wyszukiwanie binarne wymaga 13.

Algorytm

Dla każdego indeksu i od 1 do n-1 porównaj nums[i] z nums[i-1].
Jeśli nums[i] < nums[i-1], zwróć nums[i]: zaczyna się tam drugi ciąg.
Jeśli pętla się zakończy, lista nie była obrócona: zwróć nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Wyszukiwanie binarne względem ostatniej wartości

Intuicja

Trzymaj się jednej zasady: minimum znajduje się między lo a hi, włącznie. Na początku ten zakres obejmuje całą listę. Spójrz na środkową wartość i porównaj ją z nums[hi], ostatnią wartością zakresu.

Jeśli nums[mid] > nums[hi], gdzieś między mid a hi wartości maleją, a minimum to wartość znajdująca się zaraz za tym spadkiem, czyli na prawo od mid: ustaw lo = mid + 1. W przeciwnym razie nums[mid] < nums[hi] (wartości są różne), więc nums[mid..hi] rośnie i nie ma w nim spadku. Minimum to zatem nums[mid] lub jedna z wcześniejszych wartości, więc ustaw hi = mid. Nie pomijaj mid: może to być minimum. Każda z tych zmian pozwala zachować zasadę i zmniejsza zakres, a gdy lo zrówna się z hi, jedyna pozostała wartość jest minimum.

Prześledź pierwszy przykład: [11, 13, 15, 17, 2, 5, 9]. Zakres od 0 do 6 ma środek w indeksie 3, gdzie wartość wynosi 17 i jest większa niż nums[6] = 9, więc lo przyjmuje wartość 4. Zakres od 4 do 6 ma środek w indeksie 5, gdzie wartość wynosi 5 i nie jest większa niż 9, więc hi przyjmuje wartość 5. Zakres od 4 do 5 ma środek w indeksie 4, gdzie wartość wynosi 2 i nie jest większa niż 5, więc hi przyjmuje wartość 4. Zwróć nums[4] = 2.

Każdy krok dzieli zakres na pół, więc pętla wykonuje się najwyżej około log2(n) razy: 13 kroków dla 5000 elementów, przy użyciu dwóch indeksów pamięci dodatkowej.

Algorytm

Ustaw lo = 0 i hi = n-1.
Dopóki lo < hi, oblicz mid = lo + (hi - lo) / 2.
Jeśli nums[mid] > nums[hi], ustaw lo = mid + 1.
W przeciwnym razie ustaw hi = mid.
Gdy pętla się zakończy, zwróć nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Pułapki i przypadki brzegowe

Pętla ma cztery wiersze, a każdy z nich ma kuszącą, błędną wersję.

Wpisanie hi = mid - 1 w drugiej gałęzi. Ta gałąź jest wykonywana, gdy mid może wskazywać samo minimum. W [3, 1, 2] środkowa wartość 1 nie jest większa od 2, więc hi zmniejsza się do 0, a funkcja zwraca 3.
Wykonywanie pętli przy warunku lo ≤ hi. Gdy lo zrówna się z hi, mid jest równy obu, nums[mid] > nums[hi] ma wartość false, a hi = mid niczego nie zmienia: pętla nigdy się nie kończy. Zatrzymaj się, gdy zakres będzie zawierał jeden element, używając warunku lo < hi.
Porównywanie z nums[lo] zamiast z nums[hi]. W nieobróconej liście [1, 2, 3, 4, 5] środkowa wartość 3 jest większa niż nums[0] = 1, co sugeruje, że spadek znajduje się po prawej stronie, więc wyszukiwanie oddala się od prawdziwego minimum pod indeksem 0 i zwraca 4.
Zwracanie lo zamiast nums[lo]. Zadanie pyta o wartość; indeks jest odpowiedzią na inne pytanie (zobacz FAQ dotyczące liczby obrotów).
Zakładanie, że lista została obrócona. Obrót o 0 jest dozwolony, a kod szukający spadku bez przypadku awaryjnego odczytuje dane poza końcem listy lub niczego nie zwraca. Zwróć nums[0], gdy nie ma spadku.

Najczęstsze pytania4

Jaka jest złożoność czasowa znajdowania minimum w obróconej posortowanej tablicy?

Czas O(log n) i dodatkowa pamięć O(1) przy wyszukiwaniu binarnym. Każdy krok zachowuje połowę zakresu, więc lista 5000 elementów wymaga co najwyżej 13 porównań. Skanowanie w poszukiwaniu miejsca spadku ma złożoność O(n): odczytuje każdy element, gdy minimum znajduje się na końcu.

Dlaczego porównujemy nums[mid] z nums[hi], a nie z nums[lo]?

Ponieważ nums[hi] zawsze rozstrzyga, po której stronie znajduje się minimum, a nums[lo] tego nie robi. Jeśli nums[mid] > nums[hi], wartości muszą znajdować się między mid a hi; w przeciwnym razie nums[mid..hi] rośnie, a minimum znajduje się w mid lub przed nim. W przypadku nums[lo] wynik nums[mid] > nums[lo] pasuje zarówno do nieobróconej listy, w której minimum to nums[lo], jak i do obróconej, w której znajduje się ono na prawo od mid.

Jak ustalić, ile razy obrócono posortowaną tablicę?

Wykonaj to samo wyszukiwanie binarne i zwróć lo, indeks minimum, zamiast nums[lo]. Jeśli liczysz rotację jako przeniesienie ostatniego elementu na początek, ten indeks jest liczbą rotacji. Jeśli liczysz ją jako przeniesienie pierwszego elementu na koniec, tak jak w tym zadaniu, liczba wynosi (n - lo) mod n: w [11, 13, 15, 17, 2, 5, 9] minimum znajduje się pod indeksem 4, a 7 minus 4 daje 3 przeniesione wartości.

Czy wyszukiwanie binarne działa, gdy tablica zawiera duplikaty?

Nie, nie pozostaje bez zmian. W [2, 2, 2, 0, 2] nums[mid] może być równe nums[hi], a wtedy nie można wykluczyć żadnej ze stron. Zmniejszenie zakresu przez hi = hi - 1 w takim przypadku jest bezpieczne, ponieważ kopia nums[hi] pozostaje w zakresie pod indeksem mid, ale przeszukanie listy równych wartości z jedną mniejszą wartością ukrytą pośród nich kosztuje wtedy O(n).

Python

def findMin(nums):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [11, 13, 15, 17, 2, 5, 9]

Oczekiwane