Find First and Last Position of Element in Sorted Array
Du erhältst eine Liste von Ganzzahlen nums, die nicht absteigend sortiert ist, sodass ein Wert mehrfach vorkommen kann, sowie eine Ganzzahl target. Gib eine Liste mit zwei Indizes zurück, beginnend bei 0: der ersten und der letzten Position, an der target vorkommt. Falls target nicht in der Liste enthalten ist, gib [-1, -1] zurück. Strebe eine Laufzeit von O(log n) an.
Funktion
- numsinteger-array
- die sortierte Liste von Ganzzahlen, in der Werte mehrfach vorkommen können
- targetinteger
- der gesuchte Wert
- Gibt zurückinteger-array
- der erste und der letzte Index von target oder [-1, -1], falls es fehlt
Einschränkungen
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsist in nicht absteigender Reihenfolge sortiert.
Beispiele
- Eingabe
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- Ausgabe
- [1, 3]
- Erklärung
- Die drei Kopien von 5 befinden sich an den Indizes 1, 2 und 3, daher beginnt die Folge bei 1 und endet bei 3. An Index 0 steht 3 und an Index 4 steht 8, daher kann die Folge nicht weiter reichen.
- Eingabe
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- Ausgabe
- [-1, -1]
- Erklärung
- 7 würde zwischen 5 am Index 3 und 8 am Index 4 stehen, und keines von beiden ist 7. Die Liste enthält keine Kopie, daher lautet die Antwort
[-1, -1].
Weiterführende Frage
Wenn für dieselbe Liste Tausende von Abfragen nach verschiedenen Zielwerten gestellt werden, kann ein einziger vorheriger Durchlauf jede Abfrage schneller als O(log n) machen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Da
numssortiert ist, liegen alle Vorkommen vontargetdirekt nebeneinander in einem zusammenhängenden Abschnitt. Du brauchst die beiden Enden dieses Abschnitts.Eine Kopie zu finden und dann nach außen zu gehen, kann
O(n)kosten, wenn die Folge lang ist. Ändere stattdessen die binäre Suche so, dass sie nach einem Treffer weiter nach links geht: Sie hält dann beim ersten Index an, dessen Wert mindestens so groß ist wie die gesuchte Zahl.Schreibe eine Hilfsfunktion, die den ersten Index mit
nums[i] ≥ valuezurückgibt. Rufe sie mittargetauf, um den Anfang des zusammenhängenden Bereichs zu erhalten, prüfe, ob der Wert dorttargetist, und rufe sie mittarget + 1auf: Der Bereich endet einen Index davor.
Lösung
Eine einfache binäre Suche endet bei einer beliebigen Kopie von target, auf die sie trifft, und diese Kopie kann sich an jeder Stelle innerhalb des zusammenhängenden Bereichs befinden. Suche stattdessen nach einer unteren Grenze: dem ersten Index, dessen Wert mindestens einer bestimmten Zahl entspricht. Die unteren Grenzen von target und target + 1 ergeben beide Enden des zusammenhängenden Bereichs in O(log n).
Durchsuche die gesamte Liste
Idee
Gehe die Liste einmal durch. Der erste Index, an dem target steht, ist der Anfang, und der letzte ist das Ende. Wenn target nie vorkommt, bleiben beide bei -1.
Das funktioniert bei jeder Liste, sortiert oder nicht, und genau darin liegt die Schwäche: Es liest alle n Werte. Eine Liste mit 10^4 Werten kostet 10.000 Vergleiche, obwohl etwa 28 ausreichen würden.
Algorithmus
- Setze
first = last = -1. - Prüfe für jeden Index
i, obnums[i]gleichtargetist. Setzefirst = i, wennfirstnoch-1ist, und setzelast = i. - Gib
[first, last]zurück.
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]Finde eine Kopie und erweitere sie dann
Idee
Führe eine binäre Suche nach einem beliebigen Index durch, an dem target steht. Die Liste ist sortiert, daher liegen alle Vorkommen in einem zusammenhängenden Bereich um diesen Index: Gehe nach links und rechts, solange der jeweilige Nachbar noch target ist.
Die Suche benötigt O(log n), und das Durchlaufen benötigt einen Schritt pro Vorkommen, insgesamt also k Schritte. Wenn der größte Teil der Liste aus target besteht, etwa aus 10^4 Vorkommen, liest das Durchlaufen jeden Wert, und du bist wieder bei einer linearen Suche.
Algorithmus
- Führe eine binäre Suche nach einem beliebigen Index
founddurch, für dennums[found] == targetgilt. - Gibt es keinen, gib
[-1, -1]zurück. - Bewege
firstvonfoundaus nach links, solange der Wert davor gleichtargetist. - Bewege
lastvonfoundaus nach rechts, solange der Wert danach gleichtargetist. - Gib
[first, last]zurück.
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]Zwei binäre Suchläufe nach der unteren Grenze
Idee
Stelle eine andere Frage: Was ist der erste Index, dessen Wert mindestens value beträgt? Dieser Index ist die untere Grenze oder n, wenn kein Wert diese Bedingung erfüllt. Behalte einen halboffenen Bereich [lo, hi) bei, der diesen Index immer enthält. Wenn nums[mid] < value, dann sind mid und alle Werte davor zu klein. Andernfalls erfüllt mid die Bedingung, aber möglicherweise auch ein früherer Index. Daher bleibt mid im Bereich und wird zum neuen hi. Die Schleife endet bei einem Treffer nie vorzeitig.
Die untere Grenze von target ist die Stelle, an der seine Folge beginnt. Die Werte sind Ganzzahlen, daher befindet sich der erste Wert, der größer als target ist, an der unteren Grenze von target + 1, und die Folge endet einen Index davor. Im ersten Beispiel ist die untere Grenze von 5 gleich 1 und die untere Grenze von 6 gleich 4, wo 8 steht: Die Folge ist [1, 3]. Die beiden Suchen benötigen bei 10^4 Werten etwa 28 Schritte, unabhängig von der Länge der Folge.
Algorithmus
- Schreibe
lowerBound(value): beginne mitlo = 0,hi = n; whilelo < hi, ifnums[mid] < valuesetzelo = mid + 1, else setzehi = mid; returnlo. - Setze
first = lowerBound(target). - If
first == nodernums[first] != target, return[-1, -1]. - Setze
last = lowerBound(target + 1) - 1und return[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]
Stolperfallen und Grenzfälle
- Sofort zurückkehren, sobald
nums[mid] == targetgilt. Dieser Index kann irgendwo im Bereich liegen: In[3, 5, 5, 5, 8]ist der erste Mittelpunkt Index 2, also weder das eine noch das andere Ende. - Bei der Untergrenzensuche
hi = mid - 1schreiben, wennnums[mid] ≥ valuegilt. Dadurch wirdmidverworfen, obwohl es die Antwort sein könnte. nums[first]lesen, ohnefirst < nzu überprüfen. Wenntargetgrößer als jeder Wert ist, wie es in den Beispielen bei 13 der Fall wäre, ist die Untergrenzen, also eine Position hinter dem Ende.- Die Verschiebung in Lua und R vergessen. Ihre Listen beginnen bei 1, also musst du von beiden Positionen 1 abziehen.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität beim Finden der ersten und letzten Position?
O(log n) Zeitaufwand und O(1) Speicherplatz mit zwei binären Suchen. Keine der beiden beendet die Suche bei einem Treffer, daher hängen die Kosten nicht davon ab, wie viele Kopien des Zielwerts vorhanden sind: etwa 14 Schritte pro Suche bei 10^4 Werten.
Was ist eine untere Schranke bei der binären Suche?
Die Untergrenze eines Werts ist der erste Index, dessen Element mindestens diesem Wert entspricht, oder die Länge der Liste, falls es keinen solchen Index gibt. An dieser Stelle würde der Wert eingefügt werden, damit die Liste sortiert bleibt. Die Obergrenze ist der erste Index, dessen Element strikt größer ist.
Kann eine binäre Suchfunktion sowohl den ersten als auch den letzten Index finden?
Ja. Gib der Suche ein Flag: Bei einem Treffer speicherst du den Index und suchst weiter nach links für das erste Vorkommen oder nach rechts für das letzte. Eine Suche nach der unteren Grenze für target und für target + 1 funktioniert ebenfalls. Beide laufen in O(log n).
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def searchRange(nums, target):
# Schreibe hier den CodeTest #1
Test #2
Argumente
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
Erwartete Ausgabe
[1, 3]