Algorithmusübung 5

Rotate Array

Erläuterung

Wenn zwei Argumente übergeben werden, ein Array vom Typ Integer und eine Ganzzahl N (Anzahl der Umdrehungen), werden die Elemente des Arrays N-mal verschoben (minus nach links plus nach rechts). Machen wir es zu einem gedrehten Array.

Beispiel

Angenommen, die folgende Sequenz wird übergeben. Wenn die Drehzahl N -1 ist, werden alle Elemente nacheinander nach links verschoben. Wenn die Anzahl der Umdrehungen N 2 beträgt, werden alle Elemente zweimal nacheinander nach rechts verschoben.

Try It Yourself (Brute Force) Das erste, was mir zu diesem Thema in den Sinn kam, war der Brute-Force-Algorithmus nach der Rotation Links und rechts befinden sich immer zwei Teilarrays. Erstellen Sie also diese beiden Arrays. (Im Fall von N = 2 im Beispiel ist left_sub_array = {9, 40} und right_sub_array = {1, 10, 20, 0, 59, 86, 32, 11}) Dann werden die gedrehten Elemente, die in den linken und rechten Teilarrays gespeichert sind, nacheinander auf das ursprüngliche Array aktualisiert. Wenn N negativ ist, kann die Linksrotation auf den Rechtsrotationsalgorithmus angewendet werden.

Laufzeitkomplexität O (n)

Raumberechnung (Speicherkomplexität) O (n)

Implementierung

TEST

OUTPUT

Rezension

Um die Reihenfolge der Elemente zu ändern, müssen die Positionen aller Elemente neu angeordnet werden, sodass die Ausführungszeit O (n) die Grenze ist. Der Umfang der räumlichen Berechnung kann jedoch O (1) sein. Das heißt, es wird nur die übergebene Datenstruktur verwendet.

Optimierung: Speicherkomplexität O (n) -> O (1)

1. Invertieren Sie die Elemente des ursprünglichen Arrays.
2. Invertieren Sie die Elemente von 0 nach N-1.
3. Invertieren Sie die Elemente von N nach Länge-1

Beispiel

Angenommen, die gleiche Sequenz wie im vorherigen Beispiel wird übergeben. Die Anzahl der Umdrehungen beträgt N = 2.

1. Invertieren Sie zunächst alle Elemente des ursprünglichen Arrays.
2. Invertieren Sie dann die Elemente von Index 0 zu N-1 (2-1 = 1).
3. Invertieren Sie schließlich die Elemente von N (2) bis zum Ende des Arrays. Jetzt kann der Umfang der räumlichen Berechnung mit der Konstanten O (1) optimiert werden.

Implementierung

AUSGABE (gleicher TEST-Code)