Find First and Last Position of Element in Sorted Array
Otrzymujesz listę liczb całkowitych nums posortowaną w kolejności niemalejącej, więc wartości mogą się powtarzać, oraz liczbę całkowitą target. Zwróć listę dwóch indeksów, liczonych od 0: pierwszą i ostatnią pozycję, na której pojawia się target. Jeśli target nie ma na liście, zwróć [-1, -1]. Dąż do złożoności czasowej O(log n).
Funkcja
- numsinteger-array
- posortowana lista liczb całkowitych, w której wartości mogą się powtarzać
- targetinteger
- wartość, której należy szukać
- Zwracainteger-array
- pierwszy i ostatni indeks elementu target lub [-1, -1], jeśli go nie ma
Ograniczenia
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsjest posortowane w kolejności niemalejącej.
Przykłady
- Wejście
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- Wyjście
- [1, 3]
- Wyjaśnienie
- Trzy kopie liczby 5 znajdują się pod indeksami 1, 2 i 3, więc ciąg zaczyna się od indeksu 1 i kończy na indeksie 3. Pod indeksem 0 znajduje się 3, a pod indeksem 4 — 8, więc ciąg nie może sięgać dalej.
- Wejście
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- Wyjście
- [-1, -1]
- Wyjaśnienie
- 7 znajdowałaby się między 5 na indeksie 3 a 8 na indeksie 4, a żadna z tych wartości nie jest równa 7. Lista nie zawiera żadnego wystąpienia 7, więc odpowiedź to
[-1, -1].
Pytanie dodatkowe
Czy jeśli ta sama lista otrzymuje tysiące zapytań dotyczących różnych wartości docelowych, jedno wcześniejsze przejście po niej może sprawić, że każde zapytanie będzie szybsze niż O(log n)?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Ponieważ
numsjest posortowane, wszystkie wystąpieniatargetznajdują się obok siebie w jednym ciągu. Potrzebujesz obu końców tego ciągu.Znalezienie jednej kopii i przechodzenie na zewnątrz może kosztować
O(n), gdy seria jest długa. Zamiast tego zmień wyszukiwanie binarne tak, aby po znalezieniu dopasowania kontynuowało w lewo: zatrzyma się wtedy na pierwszym indeksie, którego wartość jest co najmniej równa szukanej liczbie.Napisz jedną funkcję pomocniczą, która zwraca pierwszy indeks, dla którego
nums[i] ≥ value. Wywołaj ją z argumentemtarget, aby uzyskać początek serii, sprawdź, czy wartość pod tym indeksem totarget, a następnie wywołaj ją z argumentemtarget + 1: seria kończy się o jeden indeks wcześniej.
Rozwiązanie
Zwykłe wyszukiwanie binarne zatrzymuje się na dowolnym wystąpieniu target, na które trafi, a to wystąpienie może znajdować się w dowolnym miejscu ciągu. Zamiast tego wyszukaj dolną granicę: pierwszy indeks, którego wartość jest co najmniej równa podanej liczbie. Dolne granice target i target + 1 wyznaczają oba końce ciągu w O(log n).
Skanuj całą listę
Intuicja
Przejdź raz przez listę. Pierwszy indeks, pod którym znajduje się target, jest początkiem, a ostatni — końcem. Jeśli target nigdy się nie pojawi, oba pozostaną równe -1.
To działa na każdej liście, posortowanej lub nie, i na tym polega wada tego rozwiązania: odczytuje wszystkie n wartości. Lista zawierająca 10^4 wartości wymaga 10 000 porównań, choć wystarczyłoby około 28.
Algorytm
- Ustaw
first = last = -1. - Dla każdego indeksu
i, jeślinums[i]jest równytarget, ustawfirst = i, gdyfirstnadal wynosi-1, i ustawlast = i. - Zwróć
[first, last].
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]Znajdź jedną kopię, a następnie rozwiń
Intuicja
Wyszukaj binarnie dowolny indeks zawierający target. Lista jest posortowana, więc wszystkie kopie znajdują się w jednym nieprzerwanym ciągu wokół tego indeksu: przesuwaj się w lewo i w prawo, dopóki sąsiad nadal ma wartość target.
Wyszukiwanie zajmuje O(log n), a przejście wymaga jednego kroku na każdą kopię, łącznie k kroków. Gdy większość listy ma wartość target, na przykład 10^4 kopii, przejście odczytuje każdą wartość i wracasz do wyszukiwania liniowego.
Algorytm
- Przeprowadź wyszukiwanie binarne, aby znaleźć dowolny indeks
found, dla któregonums[found] == target. - Jeśli go nie ma, zwróć
[-1, -1]. - Przesuwaj
firstw lewo odfound, dopóki poprzedzająca go wartość jest równatarget. - Przesuwaj
lastw prawo odfound, dopóki następująca po nim wartość jest równatarget. - Zwróć
[first, last].
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]Dwa wyszukiwania binarne dolnej granicy
Intuicja
Zadaj inne pytanie: jaki jest pierwszy indeks, którego wartość jest co najmniej równa value? Ten indeks to dolna granica albo n, jeśli żadna wartość nie spełnia tego warunku. Utrzymuj przedział półotwarty [lo, hi), który zawsze go zawiera. Jeśli nums[mid] < value, to mid i wszystkie indeksy przed nim mają zbyt małe wartości. W przeciwnym razie mid spełnia warunek, ale wcześniejszy indeks też może go spełniać, więc mid pozostaje w przedziale jako nowe hi. Pętla nigdy nie kończy się wcześniej po znalezieniu pasującej wartości.
Dolna granica target wskazuje początek jego serii. Wartości są liczbami całkowitymi, więc pierwsza wartość większa niż target znajduje się na dolnej granicy target + 1, a seria kończy się o jeden indeks wcześniej. W pierwszym przykładzie dolna granica 5 wynosi 1, a dolna granica 6 wynosi 4, gdzie znajduje się 8: seria to [1, 3]. Te dwa wyszukiwania zajmują około 28 kroków dla 10^4 wartości, niezależnie od długości serii.
Algorytm
- Napisz
lowerBound(value): zacznij odlo = 0,hi = n; dopókilo < hi, jeślinums[mid] < value, ustawlo = mid + 1, w przeciwnym razie ustawhi = mid; zwróćlo. - Ustaw
first = lowerBound(target). - Jeśli
first == nlubnums[first] != target, zwróć[-1, -1]. - Ustaw
last = lowerBound(target + 1) - 1i zwróć[first, last].
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
Pułapki i przypadki brzegowe
- Zwracanie wyniku od razu, gdy
nums[mid] == target. Ten indeks może znajdować się w dowolnym miejscu ciągu: w[3, 5, 5, 5, 8]pierwsza wartość środkowa ma indeks 2, który nie jest żadnym z końców. - Ustawianie
hi = mid - 1w wyszukiwaniu dolnej granicy, gdynums[mid] ≥ value. W ten sposób pomijaszmid, który może być odpowiedzią. - Odczytywanie
nums[first]bez sprawdzeniafirst < n. Gdytargetjest większy od każdej wartości, tak jak 13 w przykładach, dolna granica wynosin, czyli wskazuje pozycję za końcem. - Zapominanie o przesunięciu w Lua i R. Ich listy zaczynają się od 1, więc odejmij 1 od obu pozycji.
Najczęstsze pytania3
Jaka jest złożoność czasowa znajdowania pierwszej i ostatniej pozycji?
Czas O(log n) i przestrzeń O(1), przy użyciu dwóch wyszukiwań binarnych. Żadne z nich nie kończy się po znalezieniu dopasowania, więc koszt nie zależy od liczby kopii szukanej wartości: około 14 kroków na wyszukiwanie dla 10^4 wartości.
Czym jest dolna granica w wyszukiwaniu binarnym?
Dolna granica wartości to pierwszy indeks, którego element jest co najmniej równy tej wartości, albo długość listy, jeśli taki indeks nie istnieje. To miejsce, w którym należałoby wstawić tę wartość, aby lista pozostała posortowana. Górna granica to pierwszy indeks, którego element jest ściśle większy.
Czy jedna funkcja wyszukiwania binarnego może znaleźć zarówno pierwszy, jak i ostatni indeks?
Tak. Dodaj do wyszukiwania flagę: po znalezieniu dopasowania zapisz indeks i kontynuuj wyszukiwanie w lewo, aby znaleźć pierwsze wystąpienie, albo w prawo, aby znaleźć ostatnie. Zadziała też wywołanie wyszukiwania dolnej granicy dla target i target + 1. Oba działają w czasie O(log n).
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def searchRange(nums, target):
# Wpisz kod tutajTest #1
Test #2
Argumenty
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
Oczekiwany wynik
[1, 3]