HOWTO · Java
在 Java 中移动数组
这篇文章演示了在 Java 中移动数组
本页内容
移动数组可能指两种不同操作。旋转会让元素循环移动并保留所有元素；向右旋转两位会把末尾两个元素移到开头。删除开头元素则会返回较短的序列，并丢弃这些值。如果需要保留数组中的所有内容，应选择旋转；如果只想处理后缀，则应选择跳过元素。
除非另有说明，下面的示例都执行向右旋转。正数表示向右旋转，负数表示向左旋转；大于数组长度的距离可以对数组长度取模来归一化。数组长度固定，因此返回新数组的代码只有在不重新赋值或修改原数组时，才会让调用方的原数组保持不变。
下面的示例都是独立的 Java 程序，循环置换算法的示例还附有输出。
先判断你要的是旋转，还是删除开头元素
如果需要 int[] 这样的基本类型数组，可以使用循环或临时数组。如果数据已经是 List，或者引用类型数组可以作为列表使用，则可以用 Collections.rotate()。如果需要直接修改数组、不分配另一个数组，并且能够接受较复杂的代码，可以使用循环置换算法。如果要丢弃流开头的前 n 个元素，可以使用 skip()；这不是旋转，也不会保留原来的长度。
用循环原地旋转数组
这种方法每次向右移动一位。它先保存末尾的值，再将其他值向右移动，最后把保存的值放到索引零处。示例从包含五个整数的数组开始，向右旋转两位。此方法会修改传入的数组，只使用常数级额外空间；数组长度为 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 数组也包含旋转后的值。这种方式处理对象数组和列表时很简洁，但如果把基本类型数据转换成包装类型对象，就会发生装箱。
使用循环置换算法原地旋转
循环置换算法会把数组划分成多个循环。向左旋转 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，因此每个值都会原样写回。长度检查会在计算取模之前处理空数组。循环和临时数组方法更容易维护；只有确实需要常数级额外空间时，才优先考虑循环置换算法。
使用 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() 会将剩余元素收集到一个新的基本类型数组中。这种方式适合处理后缀，但会分配结果数组；如果必须保留所有元素，它就不能替代旋转。
