【详解】使用Java解决数组旋转问题
【摘要】 使用Java解决数组旋转问题问题描述给定一个包含n个整数的数组，要求将数组中的元素向前移动m个位置，即数组的前n-m个元素顺序向后移动m个位置，最后m个元素移动到数组的最前面。例如，给定数组[1, 2, 3, 4, 5]和m=2，则数组变为[4, 5, 1, 2, 3]。解决方案方法一：使用额外数组最直观的方法是使用一个额外的数组来存储旋转后的结果，然后将结果复制回原数组。这...
使用Java解决数组旋转问题
问题描述
给定一个包含n个整数的数组，要求将数组中的元素向前移动m个位置，即数组的前n-m个元素顺序向后移动m个位置，最后m个元素移动到数组的最前面。例如，给定数组[1, 2, 3, 4, 5]和m=2，则数组变为[4, 5, 1, 2, 3]。
解决方案
方法一：使用额外数组
最直观的方法是使用一个额外的数组来存储旋转后的结果，然后将结果复制回原数组。这种方法简单易懂，但需要额外的空间。
Java代码实现
public class ArrayRotate {
public static void rotate(int[] nums, int m) {
if (nums == null || nums.length == 0) return;
int n = nums.length;
m %= n; // 处理m大于n的情况
if (m == 0) return;
int[] temp = new int[m];
System.arraycopy(nums, n - m, temp, 0, m); // 复制最后m个元素到临时数组
System.arraycopy(nums, 0, nums, m, n - m); // 将前n-m个元素向后移动m个位置
System.arraycopy(temp, 0, nums, 0, m); // 将临时数组的内容复制到数组的最前面
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int m = 2;
rotate(nums, m);
for (int num : nums) {
System.out.print(num + " ");
}
}
}方法二：反转数组
更高效的方法是通过反转数组来实现旋转。具体步骤如下：
- 反转整个数组。
- 反转前m个元素。
- 反转剩余的n-m个元素。
这种方法不需要额外的空间，并且时间复杂度为O(n)。
Java代码实现
public class ArrayRotate {
public static void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
public static void rotate(int[] nums, int m) {
if (nums == null || nums.length == 0) return;
int n = nums.length;
m %= n; // 处理m大于n的情况
if (m == 0) return;
reverse(nums, 0, n - 1); // 反转整个数组
reverse(nums, 0, m - 1); // 反转前m个元素
reverse(nums, m, n - 1); // 反转剩余的n-m个元素
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int m = 2;
rotate(nums, m);
for (int num : nums) {
System.out.print(num + " ");
}
}
}
这个问题可以通过多种方式解决，这里我将提供一个使用Java实现的示例代码。这个例子中，我们将使用数组来存储这些整数，并通过循环和临时数组来实现数组元素的旋转。
问题描述
给定一个包含 n 个整数的数组 arr 和一个整数 m，我们需要将数组中的前 n-m 个元素向后移动 m 个位置，最后 m 个元素移动到数组的最前面。
示例
假设我们有一个数组 arr = [1, 2, 3, 4, 5] 和 m = 2，那么经过操作后，数组应该变为 [4, 5, 1, 2, 3]。
Java 实现
public class ArrayRotation {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int m = 2;
// 调用旋转方法
rotateArray(arr, m);
// 打印旋转后的数组
System.out.println("Rotated array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void rotateArray(int[] arr, int m) {
int n = arr.length;
if (n == 0 || m % n == 0) {
return; // 如果数组为空或m是n的倍数，不需要旋转
}
m = m % n; // 处理m大于n的情况
// 使用临时数组来存储最后m个元素
int[] temp = new int[m];
for (int i = 0; i < m; i++) {
temp[i] = arr[n - m + i];
}
// 将前n-m个元素向后移动m个位置
for (int i = n - m - 1; i >= 0; i--) {
arr[i + m] = arr[i];
}
// 将临时数组中的元素放到数组的最前面
for (int i = 0; i < m; i++) {
arr[i] = temp[i];
}
}
}代码解释
- 主方法 (
main):
- 定义一个数组
arr 和一个整数 m。 - 调用
rotateArray 方法进行数组旋转。 - 打印旋转后的数组。
- 旋转方法 (
rotateArray):
- 获取数组的长度
n。 - 检查特殊情况：如果数组为空或
m 是 n 的倍数，则直接返回。 - 计算
m % n 以处理 m 大于 n 的情况。 - 使用一个临时数组
temp 来存储数组的最后 m 个元素。 - 将数组的前
n-m 个元素向后移动 m 个位置。 - 将临时数组
temp 中的元素放到数组的最前面。
运行结果
对于输入数组 [1, 2, 3, 4, 5] 和 m = 2，输出将是：
Rotated array:
4 5 1 2 3
这个问题可以通过多种方法来解决，但这里我将介绍一种比较直观且效率较高的方法：通过三次反转数组来实现。
问题描述
给定一个整数数组 nums 和一个非负整数 m，要求将数组的前 n-m 个元素向后移动 m 个位置，最后 m 个元素移到数组的最前面。
解决方案
- 反转整个数组：首先将整个数组反转。
- 反转前
m 个元素：然后将前 m 个元素反转。 - 反转剩余的
n-m 个元素：最后将剩余的 n-m 个元素反转。
具体步骤
假设我们有一个数组 nums = [1, 2, 3, 4, 5] 和 m = 2，目标是将数组变为 [4, 5, 1, 2, 3]。
- 反转整个数组：
- 原数组：
[1, 2, 3, 4, 5] - 反转后：
[5, 4, 3, 2, 1]
- 反转前
m 个元素：
- 前
m 个元素：[5, 4] - 反转后：
[4, 5] - 当前数组：
[4, 5, 3, 2, 1]
- 反转剩余的
n-m 个元素：
- 剩余的
n-m 个元素：[3, 2, 1] - 反转后：
[1, 2, 3] - 最终数组：
[4, 5, 1, 2, 3]
Java 实现代码
public class ArrayRotation {
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int m = 2;
rotate(nums, m);
for (int num : nums) {
System.out.print(num + " ");
}
}
public static void rotate(int[] nums, int m) {
if (nums == null || nums.length == 0 || m < 0) {
throw new IllegalArgumentException("Invalid input");
}
int n = nums.length;
m = m % n; // 处理 m 大于数组长度的情况
reverse(nums, 0, n - 1); // 反转整个数组
reverse(nums, 0, m - 1); // 反转前 m 个元素
reverse(nums, m, n - 1); // 反转剩余的 n-m 个元素
}
private static void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}代码解释
- 主函数
main：
- 初始化数组
nums 和旋转次数 m。 - 调用
rotate 方法进行数组旋转。 - 打印旋转后的数组。
- 旋转方法
rotate：
- 检查输入的有效性。
- 计算实际需要旋转的步数
m（处理 m 大于数组长度的情况）。 - 调用
reverse 方法三次，分别反转整个数组、前 m 个元素和剩余的 n-m 个元素。
- 反转方法
reverse：
- 使用双指针法交换数组中的元素，从两端向中间逐步交换。
这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。希望这个解释对你有帮助！如果有任何问题或需要进一步的说明，请随时告诉我。
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）