Check if an Array Is Sorted

Q: Warum reicht es aus, die Nachbarn zu überprüfen?

Die Ordnungsrelation ist transitiv: Wenn a ≤ b und b ≤ c , dann gilt a ≤ c . Wenn also jedes benachbarte Paar geordnet ist, sind auch alle Positionspaare geordnet. Umgekehrt hat jedes unsortierte Array mindestens ein benachbartes Paar, bei dem der Wert abnimmt.

Q: Ist ein Array mit gleichen Elementen sortiert?

Ja, in nicht absteigender Reihenfolge: [4, 4, 4] ist sortiert, da kein Element größer als das nächste ist. Wenn eine Aufgabe stattdessen eine streng aufsteigende Reihenfolge verlangt, ändere die Prüfung so, dass auch gleiche Nachbarn abgelehnt werden.

Q: Kann ich eine Kopie sortieren und mit dem Original vergleichen?

Ja, und es liefert die richtige Antwort, aber es benötigt O(n log n) Zeit und O(n) zusätzlichen Speicher für die Kopie. Die Prüfung der Nachbarn ist schneller, benötigt keine Kopie und kann bereits beim ersten Schritt nach unten zurückkehren, ohne den Rest zu lesen.

EinsteigerArrays und Strings

+10

Du erhältst ein Array aus ganzen Zahlen nums. Gib true zurück, wenn es in nicht absteigender Reihenfolge sortiert ist, das heißt, jedes Element kleiner oder gleich dem darauf folgenden ist, und andernfalls false. Gleiche benachbarte Elemente sind in Ordnung: [2, 2, 3] gilt als sortiert. Ein Array mit einem Element ist sortiert.

Funktion

isSorted(nums: integer-array) → boolean

numsinteger-array: das zu überprüfende Integer-Array
Gibt zurückboolean: wahr, wenn jedes Element kleiner oder gleich dem jeweils nächsten ist, andernfalls falsch

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Beispiele

Eingabe: nums = [1, 3, 3, 7]
Ausgabe: true
Erklärung: Jeder Schritt geht nach oben oder bleibt auf demselben Niveau: 1 auf 3, 3 auf 3, 3 auf 7. Die wiederholte 3 ist erlaubt, also lautet die Antwort true.

Eingabe: nums = [2, 5, 4, 9]
Ausgabe: false
Erklärung: Der Schritt von 5 auf 4 geht nach unten. Ein solcher Schritt reicht aus, um das Array unsortiert zu machen, obwohl 9 am Ende der größte Wert ist. Die Antwort lautet also false.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du ein Array, das entweder aufsteigend oder absteigend sortiert sein kann, mit nur einem Durchlauf überprüfen?

Tipps

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

0 von 3 geöffnet

Lösung

Ein Array ist genau dann sortiert, wenn kein Element größer ist als das unmittelbar darauf folgende. Du musst nie Elemente vergleichen, die weit auseinanderliegen: Wenn jedes benachbarte Paar in der richtigen Reihenfolge ist, ist es das ganze Array auch. Dadurch wird die Prüfung zu einem einzigen Durchlauf über n-1 Paare, der beim ersten Rückschritt enden kann.

Eine Kopie sortieren und vergleichen

Idee

Ein sortiertes Array ist eines, das sich durch das Sortieren nicht ändern würde. Erstelle also eine Kopie von nums, sortiere die Kopie und prüfe, ob sie an jeder Position mit dem Original übereinstimmt. Wenn alle Positionen übereinstimmen, war nums bereits sortiert.

Für [2, 5, 4, 9] lautet die sortierte Kopie [2, 4, 5, 9]. An Position 1 steht im Original eine 5 und in der Kopie eine 4, daher lautet die Antwort false. Für [1, 3, 3, 7] ist die Kopie identisch und die Antwort lautet true.

Das ist korrekt, aber es geht über das hinaus, was die Frage verlangt. Das Sortieren kostet O(n log n), also etwa 6 × 10^4 Vergleiche für 5000 Zahlen, und die Kopie benötigt O(n) Speicher. Außerdem wird immer das ganze Array durchlaufen, selbst wenn bereits das allererste Paar nicht sortiert ist.

Algorithmus

Kopiere nums, damit das Original unverändert bleibt.
Sortiere die Kopie in aufsteigender numerischer Reihenfolge.
Vergleiche die Kopie Position für Position mit nums.
Gib true zurück, wenn jede Position übereinstimmt, andernfalls false.

def isSorted(nums):
    # sorted returns a new list, so nums itself is left as it was.
    return sorted(nums) == nums

Vergleiche jedes benachbarte Paar

Idee

Du brauchst die sortierte Version nicht, um festzustellen, ob das Array sortiert ist. Ein Array ist genau dann nicht absteigend sortiert, wenn jedes Element höchstens so groß ist wie das direkt folgende. Da sich ≤ verkettet (a ≤ b und b ≤ c ergeben a ≤ c), deckt die Prüfung der n-1 benachbarten Paare alle Positionspaare ab.

Gehe i von 1 bis n-1 durch und vergleiche nums[i-1] mit nums[i]. Bei [2, 5, 4, 9] ist das Paar (2, 5) in Ordnung, aber beim Paar (5, 4) geht es abwärts. Daher gibst du sofort false zurück, ohne 9 anzusehen. Gleiche Nachbarn sind zulässig, denn nur > schlägt fehl.

Jedes Paar wird einmal verglichen, also beträgt die Laufzeit O(n). Der Schleifenindex ist der einzige zusätzliche Speicherbedarf: O(1). Vergleiche die beiden Werte direkt, statt sie voneinander abzuziehen: Bei Werten bis zu 10^9 kann eine Differenz einen 32-Bit-Integer überlaufen lassen.

Algorithmus

Durchlaufe die Schleife für i von 1 bis n-1.
Falls nums[i-1] > nums[i] gilt, gib false zurück.
Wenn die Schleife beendet ist, gib true zurück. Bei einem einzelnen Element wird die Schleife übersprungen, und die Liste ist sortiert.

def isSorted(nums):
    for i in range(1, len(nums)):
        # One step down anywhere breaks the order.
        if nums[i - 1] > nums[i]:
            return False
    return True

Stolperfallen und Grenzfälle

Die Schleife ist kurz, daher stecken die Fehler an ihren Rändern und im Vergleich.

Gleiche Nachbarn als Fehler behandeln. Der Test nums[i-1] >= nums[i] weist [1, 3, 3, 7] zurück. Nur ein strikt absteigender Schritt (>) verletzt die Reihenfolge.
Über das Ende hinaus lesen. Eine Schleife von 0 bis n-1, die nums[i] mit nums[i+1] vergleicht, muss eine Position früher enden, sonst liest sie außerhalb des Arrays. Bei i = 1 zu beginnen und mit i-1 zu vergleichen, vermeidet das Problem.
Subtrahieren statt vergleichen. nums[i] - nums[i-1] >= 0 sieht gleich aus, aber 10^9 - (-10^9) = 2 × 10^9 passt nicht in einen 32-Bit-int und läuft zu einer negativen Zahl über, sodass [-1000000000, 1000000000] als unsortiert gemeldet wird. Derselbe Überlauf verursacht Probleme bei einem qsort-Vergleich, der als x - y geschrieben ist.
Zahlen als Text sortieren. In JavaScript setzt sort() ohne Vergleichsfunktion 10 vor 9, sodass eine Sortier-und-Vergleich-Prüfung falsche Ergebnisse liefert.

Häufige Fragen4

Wie überprüfst du, ob ein Array sortiert ist?

Vergleiche jedes Element mit dem nächsten. Wenn ein Element größer als sein rechter Nachbar ist, ist das Array nicht sortiert und du kannst aufhören; wenn du das Ende erreichst, ohne ein solches Element zu finden, ist es sortiert. Das dauert O(n) und benötigt O(1) zusätzlichen Speicherplatz.

Warum reicht es aus, die Nachbarn zu überprüfen?

Die Ordnungsrelation ist transitiv: Wenn a ≤ b und b ≤ c, dann gilt a ≤ c. Wenn also jedes benachbarte Paar geordnet ist, sind auch alle Positionspaare geordnet. Umgekehrt hat jedes unsortierte Array mindestens ein benachbartes Paar, bei dem der Wert abnimmt.

Ist ein Array mit gleichen Elementen sortiert?

Ja, in nicht absteigender Reihenfolge: [4, 4, 4] ist sortiert, da kein Element größer als das nächste ist. Wenn eine Aufgabe stattdessen eine streng aufsteigende Reihenfolge verlangt, ändere die Prüfung so, dass auch gleiche Nachbarn abgelehnt werden.

Kann ich eine Kopie sortieren und mit dem Original vergleichen?

Ja, und es liefert die richtige Antwort, aber es benötigt O(n log n) Zeit und O(n) zusätzlichen Speicher für die Kopie. Die Prüfung der Nachbarn ist schneller, benötigt keine Kopie und kann bereits beim ersten Schritt nach unten zurückkehren, ohne den Rest zu lesen.

Python

def isSorted(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

nums = [1, 3, 3, 7]

Erwartet

true