Find Minimum in Rotated Sorted Array

Q: Wie hoch ist die Zeitkomplexität beim Finden des Minimums in einem gedrehten, sortierten Array?

O(log n) Laufzeit und O(1) zusätzlicher Speicherplatz mit binärer Suche. Bei jedem Schritt wird eine Hälfte des Bereichs beibehalten, daher benötigt eine Liste mit 5000 Elementen höchstens 13 Vergleiche. Die Suche nach dem Abfall ist O(n) : Sie liest jedes Element, wenn das Minimum am Ende steht.

Q: Warum vergleicht man nums[mid] mit nums[hi] und nicht mit nums[lo]?

Weil nums[hi] immer eindeutig festlegt, auf welcher Seite das Minimum liegt, nums[lo] jedoch nicht. Wenn nums[mid] > nums[hi] , müssen die Werte zwischen mid und hi liegen; andernfalls steigen die Werte in nums[mid..hi] , und das Minimum liegt bei mid oder davor. Bei nums[lo] passt das Ergebnis nums[mid] > nums[lo] sowohl zu einer nicht rotierten Liste, bei der das Minimum nums[lo] ist, als auch zu einer rotierten Liste, bei der es rechts von mid liegt.

Q: Wie findest du heraus, wie oft ein sortiertes Array rotiert wurde?

Führe dieselbe binäre Suche aus und gib lo , den Index des Minimums, anstelle von nums[lo] zurück. Wenn du eine Rotation als Verschieben des letzten Elements an den Anfang zählst, ist dieser Index die Anzahl der Rotationen. Wenn du sie, wie bei diesem Problem, als Verschieben des ersten Elements ans Ende zählst, ist die Anzahl (n - lo) mod n : In [11, 13, 15, 17, 2, 5, 9] liegt das Minimum am Index 4, und 7 minus 4 ergibt die 3 verschobenen Werte.

Q: Funktioniert die binäre Suche, wenn das Array Duplikate enthält?

Nicht unverändert. In [2, 2, 2, 0, 2] kann nums[mid] gleich nums[hi] sein, und dann lässt sich keine der beiden Seiten ausschließen. In diesem Fall ist es sicher, den Bereich mit hi = hi - 1 zu verkleinern, denn eine Kopie von nums[hi] bleibt bei mid im Bereich; eine Liste gleicher Werte mit einem darin versteckten kleineren Wert erfordert dann jedoch O(n) .

MittelBinäre Suche

+10

Eine Liste verschiedener Ganzzahlen wurde aufsteigend sortiert und anschließend rotiert: Eine beliebige Anzahl von Elementen, möglicherweise null, wurde vom Anfang genommen und in derselben Reihenfolge ans Ende verschoben. Zum Beispiel wird [2, 5, 9, 11, 13, 15, 17], um 3 rotiert, zu [11, 13, 15, 17, 2, 5, 9]. Du erhältst die rotierte Liste nums. Gib ihren kleinsten Wert in O(log n) Zeit zurück.

Funktion

findMin(nums: integer-array) → integer

numsinteger-array: die rotierte sortierte Liste unterschiedlicher Ganzzahlen
Gibt zurückinteger: der kleinste Wert in nums

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Alle Werte in nums sind verschieden.
nums ist eine aufsteigend sortierte Liste, die um ein gewisses k rotiert wurde, wobei 0 ≤ k < nums.length gilt; k = 0 lässt sie unrotiert.

Beispiele

Eingabe: nums = [11, 13, 15, 17, 2, 5, 9]
Ausgabe: 2
Erklärung: Die Werte steigen von 11 auf 17 und fallen dann auf 2, wo der zweite Durchlauf beginnt. Bei der Suche gilt 17 > 9 an Index 3, also liegt das Minimum rechts davon; dann setzen 5 ≤ 9 und 2 ≤ 5 hi zurück, bis der Bereich nur noch aus Index 4 besteht, der den Wert 2 enthält.

Eingabe: nums = [4, 7, 10, 12]
Ausgabe: 4
Erklärung: Diese Liste wurde um 0 rotiert, daher ist sie weiterhin sortiert und das Minimum ist ihr erster Wert. Jeder mittlere Wert ist höchstens so groß wie der letzte, daher bewegt sich hi weiter nach links, bis es Index 0 erreicht, der den Wert 4 enthält.

Eingabe: nums = [30, -6, 0, 8, 19]
Ausgabe: -6
Erklärung: Vier Werte wurden vom Anfang ans Ende verschoben, sodass der größte Wert, 30, jetzt an erster Stelle steht und das Minimum, -6, an Index 1 liegt. Die Suche verkleinert den Bereich auf die Indizes 0 und 1, sieht, dass 30 > -6, und verschiebt lo auf 1.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du den k-kleinsten Wert von nums in O(log n) Zeit zurückgeben, ohne es zu sortieren?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Eine rotierte sortierte Liste besteht aus zwei aufsteigenden Folgen: [11, 13, 15, 17] und danach [2, 5, 9]. Das Minimum ist der erste Wert der zweiten Folge, direkt nach der einzigen Stelle, an der die Werte abnehmen. Beim Durchlaufen der Liste findet man diesen Abfall in O(n). Der Vergleich eines mittleren Werts mit dem letzten Wert des Bereichs zeigt, auf welcher Seite des Abfalls sich der mittlere Wert befindet, sodass die binäre Suche ihn in O(log n) findet.

Gehe weiter, bis die Werte sinken

Idee

In einer sortierten Liste ist jeder Wert größer als der vorherige. Durch das Rotieren der Liste bleiben beide Teilfolgen sortiert, und es entsteht genau eine Stelle, an der das nicht gilt: Auf den größten Wert folgt der kleinste. Gehe also von links nach rechts und gib den ersten Wert zurück, der kleiner ist als sein linker Nachbar. Gibt es keinen solchen Wert, wurde die Liste um 0 Stellen rotiert und das Minimum ist nums[0].

In [11, 13, 15, 17, 2, 5, 9] geht der Durchlauf an 13, 15 und 17 vorbei, die jeweils größer als der vorherige Wert sind, und hält bei Index 4 an, wo 2 kleiner als 17 ist. Das ist bereits besser, als das Minimum aller Werte zu bestimmen, denn der Durchlauf hält beim Abfall an, aber dieser kann sich an jeder Stelle befinden. Wenn die Rotation ein Element verschoben hat, wie in [2, 3, 4, 5, 6, 7, 8, 1], durchläuft der Algorithmus die gesamte Liste: 5000 Vergleiche bei 5000 Elementen, während die binäre Suche 13 benötigt.

Algorithmus

Vergleiche für jeden Index i von 1 bis n-1 nums[i] mit nums[i-1].
Wenn nums[i] < nums[i-1], gib nums[i] zurück: Dort beginnt der zweite Lauf.
Wenn die Schleife endet, wurde die Liste nicht rotiert: Gib nums[0] zurück.

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

Binäre Suche nach dem letzten Wert

Idee

Halte ein Versprechen ein: Das Minimum liegt einschließlich der Grenzen zwischen lo und hi. Zu Beginn umfasst dieser Bereich die ganze Liste. Betrachte den mittleren Wert und vergleiche ihn mit nums[hi], dem letzten Wert des Bereichs.

Wenn nums[mid] > nums[hi], fallen die Werte irgendwo zwischen mid und hi, und das Minimum ist der Wert direkt nach diesem Abfall; es liegt also rechts von mid: Setze lo = mid + 1. Andernfalls gilt nums[mid] < nums[hi] (die Werte sind verschieden), also steigt nums[mid..hi] durchgehend an. Das Minimum ist dann nums[mid] oder ein Wert davor, also setze hi = mid. Überspringe mid nicht: Es könnte das Minimum sein. Beide Änderungen halten das Versprechen ein und verkleinern den Bereich. Wenn lo und hi aufeinandertreffen, ist der einzige verbleibende Wert das Minimum.

Verfolge das erste Beispiel, [11, 13, 15, 17, 2, 5, 9]. Der Bereich von 0 bis 6 hat die Mitte 3, den Wert 17, der größer ist als nums[6] = 9; daher wird lo auf 4 gesetzt. Der Bereich von 4 bis 6 hat die Mitte 5, den Wert 5, der nicht größer als 9 ist; daher wird hi auf 5 gesetzt. Der Bereich von 4 bis 5 hat die Mitte 4, den Wert 2, der nicht größer als 5 ist; daher wird hi auf 4 gesetzt. Gib nums[4] = 2 zurück.

Bei jedem Schritt halbiert sich der Bereich, daher läuft die Schleife höchstens ungefähr log2(n) Mal: 13 Schritte bei 5000 Elementen, mit zwei Indizes zusätzlichem Speicher.

Algorithmus

Setze lo = 0 und hi = n-1.
Solange lo < hi gilt, berechne mid = lo + (hi - lo) / 2.
Wenn nums[mid] > nums[hi] gilt, setze lo = mid + 1.
Andernfalls setze hi = mid.
Wenn die Schleife endet, gib nums[lo] zurück.

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]

Stolperfallen und Grenzfälle

Die Schleife ist vier Zeilen lang, und jede Zeile hat eine verlockende falsche Variante.

Im zweiten Zweig hi = mid - 1 schreiben. Dieser Zweig wird ausgeführt, wenn mid selbst das Minimum sein könnte. In [3, 1, 2] ist der mittlere Wert 1 nicht größer als 2, also sinkt hi auf 0 und die Funktion gibt 3 zurück.
Mit lo ≤ hi schleifen. Sobald lo gleich hi ist, ist mid gleich beiden, nums[mid] > nums[hi] ist falsch, und hi = mid ändert nichts: Die Schleife endet nie. Beende die Suche, wenn der Bereich nur noch ein Element enthält, also mit lo < hi.
Mit nums[lo] statt mit nums[hi] vergleichen. In der nicht rotierten Liste [1, 2, 3, 4, 5] ist der mittlere Wert 3 größer als nums[0] = 1. Das sieht so aus, als läge der Abfall rechts, also bewegt sich die Suche vom tatsächlichen Minimum an Index 0 weg und gibt 4 zurück.
lo statt nums[lo] zurückgeben. Gefragt ist nach dem Wert; der Index ist die Antwort auf eine andere Frage (siehe FAQ zur Anzahl der Rotationen).
Annehmen, dass die Liste rotiert wurde. Eine Rotation um 0 ist zulässig, und Code, der ohne Rückfalloption nach einem Abfall sucht, liest über das Ende hinaus oder gibt nichts zurück. Gib nums[0] zurück, wenn kein Abfall existiert.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Finden des Minimums in einem gedrehten, sortierten Array?

O(log n) Laufzeit und O(1) zusätzlicher Speicherplatz mit binärer Suche. Bei jedem Schritt wird eine Hälfte des Bereichs beibehalten, daher benötigt eine Liste mit 5000 Elementen höchstens 13 Vergleiche. Die Suche nach dem Abfall ist O(n): Sie liest jedes Element, wenn das Minimum am Ende steht.

Warum vergleicht man nums[mid] mit nums[hi] und nicht mit nums[lo]?

Weil nums[hi] immer eindeutig festlegt, auf welcher Seite das Minimum liegt, nums[lo] jedoch nicht. Wenn nums[mid] > nums[hi], müssen die Werte zwischen mid und hi liegen; andernfalls steigen die Werte in nums[mid..hi], und das Minimum liegt bei mid oder davor. Bei nums[lo] passt das Ergebnis nums[mid] > nums[lo] sowohl zu einer nicht rotierten Liste, bei der das Minimum nums[lo] ist, als auch zu einer rotierten Liste, bei der es rechts von mid liegt.

Wie findest du heraus, wie oft ein sortiertes Array rotiert wurde?

Führe dieselbe binäre Suche aus und gib lo, den Index des Minimums, anstelle von nums[lo] zurück. Wenn du eine Rotation als Verschieben des letzten Elements an den Anfang zählst, ist dieser Index die Anzahl der Rotationen. Wenn du sie, wie bei diesem Problem, als Verschieben des ersten Elements ans Ende zählst, ist die Anzahl (n - lo) mod n: In [11, 13, 15, 17, 2, 5, 9] liegt das Minimum am Index 4, und 7 minus 4 ergibt die 3 verschobenen Werte.

Funktioniert die binäre Suche, wenn das Array Duplikate enthält?

Nicht unverändert. In [2, 2, 2, 0, 2] kann nums[mid] gleich nums[hi] sein, und dann lässt sich keine der beiden Seiten ausschließen. In diesem Fall ist es sicher, den Bereich mit hi = hi - 1 zu verkleinern, denn eine Kopie von nums[hi] bleibt bei mid im Bereich; eine Liste gleicher Werte mit einem darin versteckten kleineren Wert erfordert dann jedoch O(n).

Python

def findMin(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet