HOWTO · Java
在 Java 中移動陣列
這篇文章演示了在 Java 中移動陣列
本頁內容
移動陣列可能指兩種不同的操作。旋轉會讓元素循環移動並保留所有元素；向右旋轉兩格會把最後兩個元素移到最前面。略過開頭元素則會傳回較短的序列，並捨棄那些值。若要保留陣列中的所有內容，請選擇旋轉；若目的是只處理後綴部分，請選擇略過元素。
除非另有說明，以下範例都採用向右旋轉。正距離表示向右旋轉，負距離表示向左旋轉；大於陣列長度的距離可以用陣列長度取模來縮減。陣列長度固定，因此傳回新陣列的程式碼只有在沒有重新指派或修改原陣列時，才會讓呼叫端的原始陣列保持不變。
以下範例都是獨立的 Java 程式，並附有 juggling 範例的輸出。
判斷你要的是旋轉還是移除開頭元素
若需要 int[] 這類基本型別陣列，請使用迴圈或暫存陣列。若資料已經是 List，或參考型別陣列可以視為清單，請使用 Collections.rotate()。若需要修改原陣列而不配置另一個陣列，且能接受較複雜的程式碼，請使用 juggling 演算法。若要捨棄串流開頭的前 n 個元素，請使用 skip()；這不是旋轉，也不會保留原本的長度。
使用迴圈原地旋轉陣列
這個方法每次向右移動一格。它會先儲存最後一個值，再將其他值向右移，最後把儲存的值放到索引 0。範例從五個整數開始，向右旋轉兩格。此方法會修改傳入的陣列，額外空間為常數；若陣列長度為 n，正規化後的距離為 k，執行時間則為 O(n × k)。
執行此範例：
本節中的程式碼以及顯示的標籤或輸出仍為英文。
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 會將正距離和負距離正規化為從零到陣列長度減一之間的值。長度檢查可避免除以零，並讓空陣列保持不變。正規化後的距離若為零，陣列也會保持不變。這種逐次移動的方法適合距離較小的情況；若陣列或距離較大，接下來兩種陣列方法都只會移動每個元素一次。
使用暫存陣列進行旋轉
若需要直接對應索引，且可以使用 O(n) 的額外儲存空間，請配置第二個陣列。向右旋轉時，先將距離正規化為 steps，即可處理負距離和超出陣列長度的距離。原本位於索引 i 的元素會移至 ((long) i + steps) % n；中間使用 long，可避免相加有效的 int 索引時發生溢位。空陣列應在使用取模之前直接返回。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
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));
}
}
目的地公式會讓超出最後一個位置的索引繞回開頭。對任何有效的 Java 陣列長度而言，long 加總都不會超出範圍；取模後的目的地則會介於零與 values.length - 1 之間。對陣列長度取模後加上相同的正規化 steps，會形成一對一的索引對應，因此每個來源索引都會對應到不同的目的地，且相對順序會保留。來源陣列不會改變；若希望改用旋轉後的陣列，請以傳回的陣列取代原陣列。
使用 Collections.rotate() 旋轉清單
Collections.rotate() 的操作對象是 List；正距離表示向右旋轉，負距離表示向左旋轉。對參考型別陣列而言，Arrays.asList(array) 會建立由同一個陣列支援的固定大小清單：可以替換元素，也可以旋轉，但不支援新增或移除清單元素。再將清單轉回陣列時，會得到另一個獨立陣列。int[] 等基本型別陣列無法透過 Arrays.asList 轉成 List<Integer>；請先將值裝箱，或改用適用於陣列的方法。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
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));
}
}
此處的清單和 values 指向相同的元素儲存空間，因此旋轉清單也會改變陣列中的元素順序。另行建立的 rotated 陣列也包含旋轉後的值。這種作法用於物件陣列和清單時很精簡；若將基本型別資料轉成包裝型別物件，則會發生裝箱。
使用 juggling 演算法原地旋轉
juggling 演算法會把陣列分成多個循環。向左旋轉 d 格時，每個目前索引都會讀取索引 current + d 的值，並在超出陣列長度時繞回零。程式碼可以用以下方式計算繞回後的索引，避免溢位：current >= n - d ? current - (n - d) : current + d。由於 d 已正規化為零到 n - 1 之間的值，結果會落在零到 n - 1 之間；當 d 為零時，結果就是原本的 current。獨立循環的數量為 gcd(n, d)：每個循環會沿著路徑搬移值，直到回到起始索引。此方法會執行 O(n) 次移動，額外儲存空間為 O(1)；當不適合再配置一個陣列時，這項特性可能很實用。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
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]
程式碼會先將指定的向右旋轉距離正規化為 rightSteps，再用 (n - rightSteps) % n 換算成等效的向左旋轉距離。對五個元素的陣列而言，向右旋轉距離 2 和 -2 分別會正規化為向右兩格和三格，對應的向左距離則分別是三格和兩格；Integer.MIN_VALUE 也能安全處理，因為它會先正規化再相減。向左旋轉會讀取循環中的下一個索引，並在陣列末端繞回開頭。程式碼中的條件式計算可避免在 current 與 leftDistance 的和會超過 n - 1 時直接相加；無論走哪個分支，結果都會介於零到 n - 1 之間，即使未繞回的總和會超過 Integer.MAX_VALUE 也一樣。gcd(n, leftDistance) 就是循環數量。正規化後的距離若為零，gcd(n, 0) 等於 n，而條件式計算會傳回 current，因此每個值都會原樣寫回。長度檢查會在計算取模之前處理空陣列。迴圈法和暫存陣列法較容易維護；只有在確實需要常數額外空間時，才優先考慮 juggling 演算法。
使用 Stream API 略過開頭元素
若要從結果中移除開頭的值，而不是將它們繞到末端，請使用 skip()。它會傳回包含剩餘元素的串流，因此將串流轉成陣列後，會得到較短的陣列，而且來源不會改變。略過數量等於或大於元素數量時，結果會是空的。skip() 要求數量不得為負數；若呼叫端提供的數量可能是負數，請先驗證或限制其範圍。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
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) 會建立整數串流，skip(count) 會略過最前面的 count 個元素，而 toArray() 會將剩餘元素收集到新的基本型別陣列中。這適合用來處理後綴部分，但會配置結果陣列；若必須保留所有元素，就不能用它取代旋轉。
