Squares of a Sorted Array

Q: Wie hoch ist die Zeitkomplexität von „Squares of a Sorted Array“?

Die Lösung mit zwei Zeigern läuft in O(n) -Zeit: Jeder Wert wird quadriert und einmal platziert. Quadrieren und anschließendes Sortieren kostet O(n log n) . Beide benötigen O(n) Speicher für das Ergebnis.

LeichtZwei Zeiger Sortieren

+10

Du erhältst ein Array aus ganzen Zahlen nums, das in nicht absteigender Reihenfolge sortiert ist. Es kann negative Werte enthalten. Quadriere jeden Wert und gib die Quadrate als neues Array zurück, das ebenfalls in nicht absteigender Reihenfolge sortiert ist.

Funktion

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: das sortierte Array von Ganzzahlen, negative Werte sind erlaubt
Gibt zurückinteger-array: das Quadrat jedes Werts, in nicht absteigender Reihenfolge sortiert

Einschränkungen

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums ist nicht absteigend sortiert.

Beispiele

Eingabe: nums = [-6, -2, 1, 3, 7]
Ausgabe: [1, 4, 9, 36, 49]
Erklärung: Die Quadrate in der ursprünglichen Reihenfolge sind 36, 4, 1, 9 und 49. Die negativen Werte -6 und -2 ergeben große Quadrate, daher verschiebt das Sortieren 36 ans Ende: [1, 4, 9, 36, 49].

Eingabe: nums = [-9, -4, -1]
Ausgabe: [1, 16, 81]
Erklärung: Alle Werte sind negativ, daher ergibt sich bei den Quadraten die umgekehrte Reihenfolge: Aus 81, 16, 1 wird [1, 16, 81].

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Quadrieren und Sortieren benötigt O(n log n). Kannst du das in O(n) schaffen?

Tipps

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

0 von 3 geöffnet

Lösung

Das Quadrieren behält die Reihenfolge der nicht negativen Werte bei, kehrt aber die Reihenfolge der negativen Werte um, sodass die Quadrate nicht sortiert sind. Sie erneut zu sortieren funktioniert, ignoriert aber die vorgegebene Reihenfolge. Die entscheidende Tatsache: Das größte Quadrat stammt immer von einem der beiden Enden von nums. Vergleiche die beiden Enden, setze das größere Quadrat ans Ende des Ergebnisses und bewege dich nach innen.

Quadrieren, dann sortieren

Idee

Erstelle ein neues Array mit dem Quadrat jedes Werts und sortiere es anschließend. Quadrate sind nie negativ, und durch das Sortieren werden sie geordnet, unabhängig davon, woher sie stammen.

Für [-6, -2, 1, 3, 7] sind die Quadrate [36, 4, 1, 9, 49], und das Sortieren ergibt [1, 4, 9, 36, 49].

Das Sortieren kostet O(n log n). Das ist hier schnell genug, aber dabei wird die Eingabe so behandelt, als wäre sie überhaupt nicht geordnet. Der nächste Ansatz nutzt die Reihenfolge und benötigt nur einen Durchlauf.

Algorithmus

Erstelle ein Array mit x * x für jedes x in nums.
Sortiere es in aufsteigender numerischer Reihenfolge.
Gib es zurück.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Zwei Zeiger von beiden Enden

Idee

Betrachte die Quadrate als die quadrierten Abstände von 0. In einem sortierten Array liegen die Werte mit dem größten Abstand zu 0 an den beiden Enden: der negativste Wert links und der positivste rechts. Das größte Quadrat ist also nums[left]² oder nums[right]², niemals ein Wert dazwischen.

Lass left auf 0 und right auf n-1, und fülle das Ergebnis von der letzten Position rückwärts. Vergleiche in jedem Schritt die beiden Quadrate an den Enden, schreibe das größere an die aktuelle Position und bewege den entsprechenden Zeiger nach innen. Was zwischen den Zeigern übrig bleibt, ist wieder ein sortiertes Array, daher gilt dieselbe Aussage bei jedem Schritt.

Bei [-6, -2, 1, 3, 7]: 49 ist größer als 36 und kommt an die letzte Stelle. Dann ist 36 größer als 9, 9 größer als 4, 4 größer als 1, und die 1 füllt Position 0. Das Ergebnis ist [1, 4, 9, 36, 49]. Jeder Wert wird genau einmal platziert: Laufzeit O(n), und das Ergebnis ist das einzige zusätzliche Array.

Algorithmus

Erstelle ein Ergebnisarray der Länge n. Setze left auf 0 und right auf n-1.
Gehe die Positionen pos von n-1 bis hinunter zu 0 durch.
Vergleiche nums[left]² mit nums[right]².
Schreibe das größere Quadrat an die Position pos und bewege den entsprechenden Zeiger einen Schritt nach innen.
Gib das Ergebnis zurück.

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    # the largest square left is always at one of the two ends
    for pos in range(n - 1, -1, -1):
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
    return result

Stolperfallen und Grenzfälle

Die Zwei-Zeiger-Version ist kurz, aber ein paar Details bringen sie zum Scheitern.

Das Ergebnis von vorne auffüllen. Das kleinste Quadrat liegt dort, wo sich die Werte bei 0 kreuzen, und das kann irgendwo in der Mitte sein. An den Enden findet sich nur das größte Quadrat. Fülle von hinten auf.
nums[left] mit nums[right] statt ihre Quadrate oder Absolutwerte zu vergleichen. -6 ist kleiner als 3, aber sein Quadrat ist größer.
Anhalten, wenn left auf right trifft. Wenn sie gleich sind, ist noch ein Wert nicht platziert; durchlaufe jede Position des Ergebnisses oder verwende left <= right.
Nur negative oder nur positive Eingaben. Bei [-9, -4, -1] erledigt der linke Zeiger die ganze Arbeit, und bei [2, 5, 8] der rechte. Beide müssen trotzdem eine sortierte Ausgabe liefern.
In JavaScript und TypeScript sortiert sort() Zahlen ohne Vergleichsfunktion als Text, sodass aus [1, 4, 36, 9] [1, 36, 4, 9] wird. Übergib (a, b) => a - b.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Squares of a Sorted Array“?

Die Lösung mit zwei Zeigern läuft in O(n)-Zeit: Jeder Wert wird quadriert und einmal platziert. Quadrieren und anschließendes Sortieren kostet O(n log n). Beide benötigen O(n) Speicher für das Ergebnis.

Warum kommt das größte Quadrat von einem der beiden Enden?

Ein Quadrat wächst mit dem Abstand zu 0. In einem sortierten Array ist der Wert, der am weitesten unter 0 liegt, der erste, und der Wert, der am weitesten über 0 liegt, der letzte. Jeder Wert dazwischen liegt näher an 0 als einer dieser beiden Werte, daher kann sein Quadrat nicht das größte sein.

Kannst du das Ergebnis stattdessen von vorne aus füllen?

Ja, aber zuerst musst du herausfinden, wo die Werte 0 überschreiten, zum Beispiel mit einer binären Suche. Dann bewegen sich zwei Zeiger von diesem Punkt aus nach außen, ähnlich wie beim Zusammenführen zweier sortierter Listen: Die negativen Werte werden von rechts nach links und die nicht negativen von links nach rechts gelesen. Wenn du von hinten auffüllst, entfällt die Suche, weil die Enden von Anfang an bekannt sind.

Ist „Squares of a Sorted Array“ ein Merge-Problem?

In der umgekehrten Reihenfolge, ja. Die quadrierten negativen Werte bilden eine sortierte Liste (von rechts nach links gelesen), und die quadrierten nicht negativen Werte bilden eine weitere. Sie zusammenzuführen ist der Zusammenführungsschritt von Merge Sort, weshalb dies in einem einzigen linearen Durchlauf gelingt.

Python

def sortedSquares(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

nums = [-6, -2, 1, 3, 7]

Erwartet

[1, 4, 9, 36, 49]