Find Peak Element

Q: Jaka jest złożoność czasowa funkcji Find Peak Element?

Wyszukiwanie binarne działa w czasie O(log n) i zajmuje O(1) przestrzeni, wykonując najwyżej 13 kroków dla 5000 wartości. Przejście od lewej strony ma złożoność O(n) , ponieważ może odczytać każdą parę, zanim znajdzie spadek.

Q: Czy wyszukiwanie binarne nadal działa, gdy jest kilka szczytów?

Tak, o ile sąsiednie wartości są różne, a miejsca poza oboma końcami są uznawane za niższe niż każda wartość. Zwraca jeden szczyt, niekoniecznie najwyższy. Po kroku w górę wartości muszą najpóźniej do końca zakresu zmienić kierunek na spadkowy, a pierwsza zmiana kierunku oznacza szczyt, więc strona, którą zachowuje wyszukiwanie, zawsze go zawiera.

Q: Czy szczyt zawsze jest największą wartością?

W tym zadaniu tak: tablica rośnie do jednego szczytu, a potem maleje, więc żadna inna wartość nie może być większa. W wersji z kilkoma szczytami tak nie jest, ponieważ liczy się każda wartość większa od obu sąsiadów. Dlatego wyszukiwanie porównuje sąsiednie wartości zamiast szukać maksimum.

ŚrednieWyszukiwanie binarne

+10

Tablica nums rośnie, a następnie maleje: każda wartość jest większa od poprzedniej aż do pewnego indeksu, a każda wartość za tym indeksem jest mniejsza od poprzedniej. Każda z tych części może być pusta, więc tablica może tylko rosnąć lub tylko maleć. Wartość na indeksie zwrotnym to maksimum — jedyna wartość większa od każdego ze swoich sąsiadów.

Zwróć indeks maksimum w czasie O(log n).

Funkcja

findPeakElement(nums: integer-array) → integer

numsinteger-array: wartości, które rosną do jednego szczytu, a następnie spadają
Zwracainteger: indeks szczytu

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] dla każdego poprawnego i.
nums ściśle rośnie aż do jednego indeksu, a potem ściśle maleje, więc istnieje dokładnie jeden szczyt.

Przykłady

Wejście: nums = [2, 5, 9, 4, 1]
Wyjście: 2
Wyjaśnienie: Wartości rosną kolejno do 2, 5 i 9, a następnie maleją do 4 i 1. Zmiana kierunku następuje przy 9, indeksie 2.

Pytanie dodatkowe

W siatce, w której żadne dwa sąsiednie pola nie są równe, szczyt to pole większe od maksymalnie czterech sąsiadów. Czy potrafisz go znaleźć bez odczytywania każdego pola?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Przy jednym wierzchołku wierzchołek jest największą wartością, więc jedno przejście znajduje go w O(n). Aby uzyskać O(log n), porównaj nums[mid] z nums[mid+1]: nachylenie w mid wskazuje, po której stronie wierzchołka się znajduje, dzięki czemu w każdym kroku można odrzucić połowę zakresu.

Idź dalej, aż wartości zaczną spadać

Intuicja

Przed szczytem każda wartość jest mniejsza od następnej, a od szczytu każda wartość jest większa. Szczyt to więc pierwszy indeks i, dla którego nums[i] > nums[i+1], lub ostatni indeks, jeśli tablica tylko rośnie.

Gdy szczyt znajduje się na końcu 5000 wartości, przejście wymaga 4999 porównań, podczas gdy wyszukiwanie binarne wymaga 13.

Algorytm

Dla i od 0 do n-2 porównaj nums[i] z nums[i+1].
Przy pierwszym i, dla którego nums[i] jest większe, zwróć i.
Jeśli pętla zakończy się bez spadku, zwróć n-1.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

Wyszukiwanie binarne na zboczu

Intuicja

Odczytaj jedną parę: nums[mid] i nums[mid+1]. Wzrost oznacza, że tablica nadal rośnie, co w tej tablicy ma miejsce tylko przed szczytem: szczyt znajduje się na pozycji mid+1 lub dalej. Spadek oznacza, że jesteś na szczycie lub za nim: szczyt znajduje się na pozycji mid lub wcześniej.

Utrzymuj przedział [lo, hi], w którym zawsze znajduje się szczyt. Wzrost przesuwa lo na mid+1. Spadek przesuwa hi na mid, zachowując mid, ponieważ może to być szczyt. Gdy lo zrówna się z hi, jedyny pozostały indeks wskazuje szczyt. Zaokrąglenie mid w dół utrzymuje go poniżej hi, więc mid+1 zawsze istnieje.

W pierwszym przykładzie dla mid = 2 widzimy 9 > 4, więc hi = 2; następnie dla mid = 1 widzimy 5 < 9, więc lo = 2, czyli szczyt. W przypadku 5000 wartości potrzeba najwyżej 13 kroków.

Algorytm

Ustaw lo = 0 i hi = n-1.
Gdy lo < hi, oblicz mid = lo + (hi - lo) / 2 i zaokrąglij w dół.
Jeśli nums[mid] < nums[mid+1], ustaw lo = mid + 1.
W przeciwnym razie ustaw hi = mid.
Zwróć lo.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

Pułapki i przypadki brzegowe

Ustawianie hi = mid - 1 przy zmniejszaniu zakresu. W [2, 5, 9, 4, 1] pierwsze mid wskazuje sam szczyt, a hi = 1 go pomija; wyszukiwanie zwraca 1.
Porównywanie z nums[mid-1] przy zaokrąglaniu mid w dół. mid może wynosić 0, a wtedy nie ma lewego sąsiada.
Używanie przedziału półotwartego z hi = n. Wtedy mid może wynosić n-1, a nums[mid+1] odczytuje wartość spoza zakresu — nawet przy pojedynczej wartości.
Zapominanie o przesunięciu w Lua i R. Odpowiedź nadal jest indeksem liczonym od 0, więc pozycja i jest zwracana jako i-1.

Najczęstsze pytania3

Jaka jest złożoność czasowa funkcji Find Peak Element?

Wyszukiwanie binarne działa w czasie O(log n) i zajmuje O(1) przestrzeni, wykonując najwyżej 13 kroków dla 5000 wartości. Przejście od lewej strony ma złożoność O(n), ponieważ może odczytać każdą parę, zanim znajdzie spadek.

Czy wyszukiwanie binarne nadal działa, gdy jest kilka szczytów?

Tak, o ile sąsiednie wartości są różne, a miejsca poza oboma końcami są uznawane za niższe niż każda wartość. Zwraca jeden szczyt, niekoniecznie najwyższy. Po kroku w górę wartości muszą najpóźniej do końca zakresu zmienić kierunek na spadkowy, a pierwsza zmiana kierunku oznacza szczyt, więc strona, którą zachowuje wyszukiwanie, zawsze go zawiera.

Czy szczyt zawsze jest największą wartością?

W tym zadaniu tak: tablica rośnie do jednego szczytu, a potem maleje, więc żadna inna wartość nie może być większa. W wersji z kilkoma szczytami tak nie jest, ponieważ liczy się każda wartość większa od obu sąsiadów. Dlatego wyszukiwanie porównuje sąsiednie wartości zamiast szukać maksimum.

def findPeakElement(nums):
    # Napisz tutaj kod

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 9, 4, 1]

Oczekiwany wynik