Rotate Array

Q: Was passiert, wenn k größer als die Länge des Arrays ist?

Alle n Schritte bringen das Array zurück in seine Ausgangsreihenfolge, daher sind nur k mod n Schritte relevant. Eine Drehung von [10, 20, 30] um 7 Positionen ist dasselbe wie eine Drehung um 1 Position und ergibt [30, 10, 20] . Wenn k ein Vielfaches von n ist, ändert sich das Array nicht.

Q: Wie rotiert man ein Array nach links?

Eine Linksrotation um k entspricht einer Rechtsrotation um n - (k mod n) . Bei Umkehrungen kehrst du zuerst die ersten k mod n Werte um, dann den Rest und schließlich das gesamte Array. Beide benötigen weiterhin O(n) Zeit.

MittelArrays und Strings Zwei Zeiger

+10

Du erhältst ein Array aus Ganzzahlen nums und eine Zahl k. Rotiere das Array um k Schritte nach rechts: In einem Schritt rückt jeder Wert um eine Position nach rechts, und der letzte Wert wird an den Anfang verschoben. Gib das rotierte Array zurück.

k kann viel größer sein als die Länge des Arrays.

Funktion

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: das Array von Ganzzahlen, das rotiert werden soll
kinteger: Wie viele Schritte nach rechts drehen
Gibt zurückinteger-array: nums um k Schritte nach rechts gedreht

Einschränkungen

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

Beispiele

Eingabe: nums = [4, 9, 1, 6, 3]k = 2
Ausgabe: [6, 3, 4, 9, 1]
Erklärung: Zwei Schritte nach rechts bringen die letzten beiden Werte, 6 und 3, nach vorne. Die anderen drei Werte rücken zwei Plätze nach rechts und behalten ihre Reihenfolge: [6, 3, 4, 9, 1].

Weiterführende Frage

Kannst du durch direktes Verschieben jedes Werts an die Position (i + k) mod n rotieren und den verdrängten Wert weitertragen? Wie viele Zyklen ergibt das?

Tipps

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

0 von 3 geöffnet

Lösung

Alle n Schritte kehrt das Array zu seinem Ausgangszustand zurück. Reduziere daher zunächst k, das bis zu 10^9 betragen kann, auf k mod n. Schreibe dann jeden Wert direkt an seinen endgültigen Index in ein zweites Array oder erziele dasselbe Ergebnis innerhalb des Arrays mit drei Umkehrungen und O(1) zusätzlichem Speicher.

Kopiere jeden Wert an seinen neuen Index

Idee

Nach k Schritten befindet sich der Wert am Index i an der Position (i + k) mod n. Schreibe ihn also direkt dorthin, ohne die Schritte auszuführen. Reduziere k zuerst auf k mod n: Eine Rotation um n bringt jeden Wert an seine ursprüngliche Position zurück. Bei k = 7 und n = 3 bleibt also nur ein Schritt übrig.

Ein Durchlauf platziert alle n Werte: O(n) Zeit und zusätzlich O(n) Speicher für das Ergebnis. Auf diese Weise kannst du nicht direkt in nums schreiben, da jeder Schreibvorgang einen Wert überschreiben würde, den du noch nicht verschoben hast.

Algorithmus

Setze n auf die Länge von nums und ersetze k durch k mod n.
Erstelle ein Ergebnisarray der Länge n.
Speichere für jeden Index i nums[i] an der Stelle result[(i + k) mod n].
Gib das Ergebnis zurück.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Drei In-place-Umkehrungen

Idee

Teile das Array in A, die ersten n-k Werte, und B, die letzten k Werte. Das rotierte Array besteht aus B, gefolgt von A, wobei jeder Block in seiner ursprünglichen Reihenfolge bleibt. Durch das Umkehren des gesamten Arrays werden sowohl die Reihenfolge der Blöcke als auch die Reihenfolge innerhalb jedes Blocks umgedreht. Daher steht B zuerst, ist aber rückwärts angeordnet, und dasselbe gilt für A. Durch erneutes Umkehren jedes Blocks wird die Reihenfolge innerhalb der Blöcke wiederhergestellt.

Für [4, 9, 1, 6, 3] und k = 2: Das Umkehren des gesamten Arrays ergibt [3, 6, 1, 9, 4], das Umkehren der ersten beiden Werte ergibt [6, 3, 1, 9, 4], und das Umkehren der letzten drei ergibt [6, 3, 4, 9, 1].

Jeder Wert wird höchstens zweimal vertauscht, daher beträgt die Laufzeit O(n), und der zusätzliche Speicherbedarf beschränkt sich auf einige Indexvariablen (in R O(n), da beim Ändern des Vektors durch die Umkehr-Hilfsfunktion eine Kopie erstellt wird).

Algorithmus

Setze n auf die Länge von nums und ersetze k durch k mod n.
Kehre das gesamte Array um, Indizes 0 bis n-1.
Kehre den ersten Block um, Indizes 0 bis k-1.
Kehre den zweiten Block um, Indizes k bis n-1.
Gib nums zurück.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Stolperfallen und Grenzfälle

Das k mod n vergessen. Bei k = 10^9 wird die Rotation Schritt für Schritt nie fertig, und beim Umkehren der ersten k Werte wird weit über das Ende des Arrays hinaus gelesen.
Slicing ohne Modulo. In Python gibt nums[-k:] + nums[:-k] mit k = 7 und n = 3 das Array unverändert zurück, weil beide Slices am Rand des Arrays enden.
In der falschen Reihenfolge umkehren. Werden zuerst die beiden Blöcke und zuletzt das gesamte Array umgekehrt, ergibt sich eine Linksrotation.
Off-by-one-Fehler am Blockrand: Der erste Block endet bei Index k-1 und der zweite beginnt bei k. In Lua und R, die ab 1 zählen, sind die Blöcke 1..k und k+1..n.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Rotate Array?

O(n) sowohl für den Kopieransatz als auch für die drei Umkehrungen, da jeder Wert eine konstante Anzahl von Malen verschoben wird. Wenn du k zuerst mit k mod n reduzierst, spielt ein sehr großes k keine Rolle. Eine Rotation um jeweils einen Schritt kostet stattdessen O(n × k).

Was passiert, wenn k größer als die Länge des Arrays ist?

Alle n Schritte bringen das Array zurück in seine Ausgangsreihenfolge, daher sind nur k mod n Schritte relevant. Eine Drehung von [10, 20, 30] um 7 Positionen ist dasselbe wie eine Drehung um 1 Position und ergibt [30, 10, 20]. Wenn k ein Vielfaches von n ist, ändert sich das Array nicht.

Wie rotiert man ein Array nach links?

Eine Linksrotation um k entspricht einer Rechtsrotation um n - (k mod n). Bei Umkehrungen kehrst du zuerst die ersten k mod n Werte um, dann den Rest und schließlich das gesamte Array. Beide benötigen weiterhin O(n) Zeit.

def rotate(nums, k):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

nums = [4, 9, 1, 6, 3]
k = 2

Erwartete Ausgabe

[6, 3, 4, 9, 1]