HOWTO · Java
Verschieben eines Arrays in Java
Dieser Artikel zeigt das Verschieben eines Arrays in Java
Auf dieser Seite
Ein Array zu verschieben kann zwei verschiedene Vorgänge bedeuten. Bei einer Rotation werden die Elemente im Kreis bewegt, sodass alle erhalten bleiben; bei einer Rechtsrotation um zwei Stellen wandern die letzten beiden Elemente an den Anfang. Werden stattdessen die führenden Elemente entfernt, ist die zurückgegebene Folge kürzer und diese Werte gehen verloren. Wählen Sie die Rotation, wenn der Inhalt des Arrays erhalten bleiben soll, und das Überspringen, wenn nur der verbleibende Suffix verarbeitet werden soll.
Die folgenden Beispiele verwenden, sofern nicht anders angegeben, eine Rechtsrotation. Ein positiver Abstand rotiert nach rechts, ein negativer nach links. Abstände, die größer als die Arraylänge sind, lassen sich modulo der Länge reduzieren. Arrays haben eine feste Länge. Gibt der Code ein neues Array zurück, bleibt das ursprüngliche Array des Aufrufers nur dann unverändert, wenn es nicht neu zugewiesen oder verändert wird.
Die Beispiele sind eigenständige Java-Programme. Für das Beispiel mit dem Juggling-Algorithmus ist eine Ausgabe angegeben.
Entscheiden Sie, ob Sie eine Rotation oder das Entfernen führender Elemente meinen
Verwenden Sie eine Schleife oder ein temporäres Array, wenn Sie ein primitives Array wie int[] benötigen. Verwenden Sie Collections.rotate(), wenn Ihre Daten bereits als List vorliegen oder sich ein Array aus Referenztypen als Liste verwenden lässt. Der Juggling-Algorithmus eignet sich, wenn Sie ein Array verändern müssen, ohne ein weiteres Array anzulegen, und der zusätzliche Codeaufwand akzeptabel ist. Verwenden Sie skip(), wenn die ersten n Stream-Elemente verworfen werden sollen. Das ist keine Rotation und erhält die ursprüngliche Länge nicht.
Ein Array mit einer Schleife direkt rotieren
Bei diesem Verfahren wird jeweils eine Rechtsverschiebung ausgeführt. Zuerst wird der letzte Wert gesichert, dann werden die übrigen Werte nach rechts verschoben und schließlich wird der gesicherte Wert an Index null eingesetzt. Das Beispiel beginnt mit fünf Ganzzahlen und rotiert sie um zwei Stellen nach rechts. Es verändert das übergebene Array, benötigt konstanten zusätzlichen Speicher und hat bei einer Arraylänge von n und einem normalisierten Abstand k eine Laufzeit von O(n × k).
Führen Sie dieses Beispiel aus:
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
int distance = 2;
if (values.length > 0) {
int steps = Math.floorMod(distance, values.length);
for (int step = 0; step < steps; step++) {
int last = values[values.length - 1];
for (int i = values.length - 1; i > 0; i--) {
values[i] = values[i - 1];
}
values[0] = last;
}
}
System.out.println(Arrays.toString(values));
}
}
Math.floorMod normalisiert positive und negative Abstände auf einen Wert zwischen null und einem weniger als der Arraylänge. Die Längenprüfung verhindert eine Division modulo null und lässt ein leeres Array unverändert. Auch bei einem normalisierten Abstand von null bleibt das Array unverändert. Für kleine Abstände ist dieses wiederholte Verschieben einfach. Bei großen Arrays oder Abständen verschieben die beiden folgenden Array-Verfahren jedes Element nur einmal.
In ein temporäres Array rotieren
Legen Sie ein zweites Array an, wenn Sie eine direkte Indexzuordnung wünschen und O(n) zusätzlichen Speicher verfügbar ist. Normalisieren Sie bei einer Rechtsrotation zuerst den Abstand zu steps, damit auch negative und übergroße Abstände funktionieren. Ein Element am alten Index i gelangt nach ((long) i + steps) % n; der Zwischenschritt mit long verhindert einen Überlauf beim Addieren gültiger int-Indizes. Bei einem leeren Array muss die Methode vor der Modulo-Rechnung zurückkehren.
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
int distance = 2;
int[] rotated = new int[values.length];
if (values.length > 0) {
int steps = Math.floorMod(distance, values.length);
for (int i = 0; i < values.length; i++) {
int destination = (int) (((long) i + steps) % values.length);
rotated[destination] = values[i];
}
}
System.out.println(Arrays.toString(rotated));
}
}
Die Zielformel führt Indizes, die über den letzten Platz hinausgehen, zum Anfang zurück. Die Summe vom Typ long bleibt bei jeder gültigen Arraylänge von Java im darstellbaren Bereich; die Modulo-Rechnung ergibt anschließend ein Ziel zwischen null und values.length - 1. Derselbe normalisierte Wert steps, modulo der Arraylänge addiert, bildet jeden Quellindex eindeutig auf ein Ziel ab. So erhält jedes Quellelement ein eigenes Ziel und die Reihenfolge bleibt erhalten. Das ursprüngliche Array bleibt unverändert. Soll das neue Array an seine Stelle treten, verwenden Sie den Rückgabewert.
Eine Liste mit Collections.rotate() rotieren
Collections.rotate() arbeitet mit einer List. Ein positiver Abstand rotiert nach rechts, ein negativer nach links. Bei einem Array aus Referenztypen erzeugt Arrays.asList(array) eine Liste fester Größe, die von demselben Array gestützt wird: Elemente lassen sich ersetzen und rotieren, aber das Hinzufügen oder Entfernen von Listenelementen wird nicht unterstützt. Wird die Liste zurück in ein Array umgewandelt, entsteht ein separates Array. Primitive Arrays wie int[] lassen sich mit Arrays.asList nicht in eine List<Integer> umwandeln. Wandeln Sie die Werte dafür in Wrapper-Objekte um oder verwenden Sie ein Array-Verfahren.
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
Integer[] values = {1, 2, 3, 4, 5};
List<Integer> list = Arrays.asList(values);
Collections.rotate(list, 2);
Integer[] rotated = list.toArray(new Integer[0]);
System.out.println(Arrays.toString(rotated));
}
}
Hier verweisen die Liste und values auf denselben Elementespeicher. Deshalb ändert die Rotation auch die Reihenfolge der Elemente im Array. Das separat erzeugte Array rotated enthält ebenfalls die rotierten Werte. Das ist für Objekt-Arrays und Listen knapp, primitive Werte müssen beim Umwandeln in Wrapper-Objekte jedoch geboxt werden.
Direkt im Array mit dem Juggling-Algorithmus rotieren
Der Juggling-Algorithmus teilt das Array in Zyklen auf. Bei einer Linksrotation um d Stellen liest jeder aktuelle Index den Wert am Index current + d, wobei am Arrayende zum Anfang zurückgesprungen wird. Berechnen Sie den umgebrochenen Index im Code ohne Überlauf mit current >= n - d ? current - (n - d) : current + d. Da d auf den Bereich von null bis n - 1 normalisiert ist, ergibt sich ein Index zwischen null und n - 1. Ist d null, bleibt current unverändert. Die Anzahl unabhängiger Zyklen beträgt gcd(n, d): Jeder Zyklus verschiebt Werte entlang seines Pfads, bis er zu seinem Startindex zurückkehrt. Das Verfahren führt O(n) Verschiebungen mit O(1) zusätzlichem Speicher aus. Es kann sinnvoll sein, wenn ein weiteres Array vermieden werden muss.
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
int rightDistance = 2;
int n = values.length;
if (n > 0) {
int rightSteps = Math.floorMod(rightDistance, n);
int leftDistance = (n - rightSteps) % n;
int cycles = gcd(n, leftDistance);
for (int start = 0; start < cycles; start++) {
int saved = values[start];
int current = start;
while (true) {
int next = current >= n - leftDistance
? current - (n - leftDistance)
: current + leftDistance;
if (next == start) break;
values[current] = values[next];
current = next;
}
values[current] = saved;
}
}
System.out.println(Arrays.toString(values));
}
private static int gcd(int a, int b) {
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
}
[4, 5, 1, 2, 3]
Der Code normalisiert zuerst den angeforderten Rechtsabstand zu rightSteps und berechnet daraus mit (n - rightSteps) % n den entsprechenden Linksabstand. Bei einem Array mit fünf Elementen werden die Rechtsabstände 2 und -2 zu zwei beziehungsweise drei Rechtsverschiebungen normalisiert. Daraus ergeben sich Linksabstände von drei beziehungsweise zwei; auch Integer.MIN_VALUE ist sicher, weil der Wert vor der Subtraktion normalisiert wird. Eine Linksrotation liest in jedem Zyklus vom nächsten Index und springt am Arrayende zum Anfang zurück. Die bedingte Berechnung im Code verhindert die Addition von current und leftDistance, wenn ihre Summe größer als n - 1 wäre. Beide Zweige liefern einen Index zwischen null und n - 1, selbst wenn die ungewickelte Summe Integer.MAX_VALUE überschreiten würde. gcd(n, leftDistance) gibt die Anzahl der Zyklen an. Bei normalisiertem Abstand null ist gcd(n, 0) gleich n, und die bedingte Berechnung liefert current; jeder Wert wird also unverändert zurückgeschrieben. Die Längenprüfung behandelt ein leeres Array, bevor eine Modulo-Rechnung erfolgt. Die Schleifen- und temporären Array-Verfahren sind leichter zu warten. Verwenden Sie Juggling, wenn der konstante zusätzliche Speicherbedarf tatsächlich erforderlich ist.
Führende Elemente mit der Stream-API überspringen
Verwenden Sie skip(), wenn führende Werte aus dem Ergebnis entfernt statt ans Ende verschoben werden sollen. Die Methode gibt einen Stream mit den verbleibenden Elementen zurück. Wird dieser Stream in ein Array umgewandelt, ist das Ergebnis kürzer und die Quelle bleibt unverändert. Ist der Überspring-Abstand so groß wie die Elementanzahl oder größer, entsteht ein leeres Ergebnis. skip() verlangt einen nicht negativen Wert. Prüfen oder begrenzen Sie daher einen vom Aufrufer übergebenen Wert, falls er negativ sein könnte.
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
long count = 2;
int[] remainder = Arrays.stream(values).skip(count).toArray();
System.out.println(Arrays.toString(remainder));
}
}
Arrays.stream(values) erzeugt einen Integer-Stream, skip(count) lässt dessen erste count Elemente aus und toArray() sammelt die übrigen in einem neuen primitiven Array. Das ist praktisch, wenn ein Suffix verarbeitet werden soll, legt aber ein Ergebnis-Array an und eignet sich nicht als Ersatz für eine Rotation, bei der alle Elemente erhalten bleiben.