Java详解LeetCode 热题 100(15):LeetCode 189. 轮转数组（Rotate Array）详解

1. 题目描述

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

进阶：

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

2. 理解题目

这道题要求我们将数组中的所有元素向右移动k个位置。具体来说：

• 数组中的每个元素都向右移动k个索引位置
• 数组是"循环"的，即超出数组末尾的元素会被放置到数组的开头
• 我们需要原地修改数组，而不是创建一个新数组（尽管也可以使用额外空间的解法）

关键点：

1. k可能大于数组长度，因此实际的移动次数是k % n（其中n是数组长度）
2. 向右轮转k次等同于将数组最后k个元素移动到数组开头
3. 这道题可以有多种解法，包括使用额外空间和原地（O(1)空间复杂度）算法

3. 解法一：使用额外数组

3.1 思路

最简单直观的方法是创建一个新数组，然后将原数组的每个元素放到新数组中的正确位置：

1. 创建一个与原数组相同大小的新数组
2. 对于原数组中索引为i的元素，其在新数组中的位置为(i + k) % n
3. 将新数组的内容复制回原数组

这种方法使用了O(n)的额外空间，但思路非常清晰，适合初学者理解。

3.2 Java代码实现

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;// 处理 k 大于数组长度的情况k = k % n;// 如果k为0，不需要轮转if (k == 0) {return;}// 创建一个新数组来存储轮转后的结果int[] result = new int[n];// 将原数组中的元素放入新数组的正确位置for (int i = 0; i < n; i++) {result[(i + k) % n] = nums[i];}// 将新数组的内容复制回原数组for (int i = 0; i < n; i++) {nums[i] = result[i];}}
}

3.3 代码详解

详细解释每一步的意义和实现：

int n = nums.length;// 处理 k 大于数组长度的情况
k = k % n;// 如果k为0，不需要轮转
if (k == 0) {return;
}

• 首先获取数组长度n
• 由于轮转n次会回到原始状态，所以我们只需要考虑k % n次轮转
• 如果k为0或者k是n的倍数，数组不需要变化，直接返回

// 创建一个新数组来存储轮转后的结果
int[] result = new int[n];// 将原数组中的元素放入新数组的正确位置
for (int i = 0; i < n; i++) {result[(i + k) % n] = nums[i];
}

• 创建一个与原数组相同大小的新数组
• 将原数组中索引为i的元素放到新数组中索引为(i + k) % n的位置
• 这里使用模运算是为了处理索引超出数组长度的情况

// 将新数组的内容复制回原数组
for (int i = 0; i < n; i++) {nums[i] = result[i];
}

• 最后，将临时数组中的结果复制回原数组，完成轮转操作

3.4 复杂度分析

• 时间复杂度: O(n)，其中n是数组的长度。我们需要遍历数组两次，每次遍历的时间复杂度是O(n)。
• 空间复杂度: O(n)，我们创建了一个与原数组等长的新数组。

3.5 适用场景

这种解法适用于：

• 初学者理解问题
• 代码简洁性优先于空间效率的场景
• 数组不太大的情况

4. 解法二：环状替换法（原地算法）

4.1 思路

我们可以直接在原数组上进行操作，不使用额外空间。基本思想是：

1. 从位置0开始，将当前位置的元素放到它应该去的位置（即(i + k) % n），同时记录被替换的元素
2. 然后将被替换的元素放到它应该去的位置，继续这个过程
3. 当我们回到起始位置时，我们已经完成了一个循环，需要从下一个位置开始新的循环
4. 重复这个过程，直到所有元素都被访问

这种方法不使用额外数组，但需要仔细处理访问元素的顺序。

4.2 Java代码实现

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n;// 如果k为0，不需要轮转if (k == 0) {return;}int count = 0; // 记录已经移动的元素数量// 从0开始，最多需要处理n个元素for (int start = 0; count < n; start++) {int current = start; // 当前处理的位置int prev = nums[start]; // 当前位置的值do {// 计算下一个位置int next = (current + k) % n;// 保存下一个位置的值int temp = nums[next];// 将当前值放到下一个位置nums[next] = prev;// 更新current和prev，继续下一次替换current = next;prev = temp;count++;} while (start != current); // 当回到起始位置时，一个循环结束}}
}

4.3 代码详解

环状替换的关键在于追踪元素的移动路径，确保每个元素都被移动到正确位置：

int count = 0; // 记录已经移动的元素数量// 从0开始，最多需要处理n个元素
for (int start = 0; count < n; start++) {int current = start; // 当前处理的位置int prev = nums[start]; // 当前位置的值

• count变量记录我们已经处理过的元素数量
• start表示当前循环的起始位置
• current跟踪我们当前正在处理的位置
• prev存储当前位置原来的值

do {// 计算下一个位置int next = (current + k) % n;// 保存下一个位置的值int temp = nums[next];// 将当前值放到下一个位置nums[next] = prev;// 更新current和prev，继续下一次替换current = next;prev = temp;count++;
} while (start != current); // 当回到起始位置时，一个循环结束

• 计算元素应该被放置的下一个位置：(current + k) % n
• 在替换前，保存目标位置的原始值
• 将当前值放到目标位置
• 更新current为新位置，prev为新位置原来的值
• 增加已处理元素计数
• 重复此过程，直到回到循环的起始位置

当一个循环结束（回到起始位置）时，可能还有未被访问的元素。因此，我们增加start并开始一个新的循环，直到所有元素都被处理。

4.4 复杂度分析

• 时间复杂度: O(n)，每个元素只会被移动一次，总共需要移动n次。
• 空间复杂度: O(1)，只使用了有限的几个变量，不需要额外数组。

4.5 陷阱与注意事项

环状替换法需要特别注意：

1. 处理循环长度：如果k和n有公约数，一个循环结束后可能还有元素未被访问，需要开始新的循环
2. 边界条件：确保我们处理了所有的元素（通过计数）
3. 避免原地自我覆盖：在移动元素前保存下一个位置的值

5. 解法三：数组翻转法（最优原地算法）

5.1 思路

这是最优雅且高效的解法。基本思想是：

1. 首先翻转整个数组
2. 然后翻转前k个元素
3. 最后翻转剩余的n-k个元素

这种方法不需要额外空间，操作简单明了，且易于实现。

5.2 Java代码实现

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n;// 如果k为0，不需要轮转if (k == 0) {return;}// 1. 翻转整个数组reverse(nums, 0, n - 1);// 2. 翻转前k个元素reverse(nums, 0, k - 1);// 3. 翻转剩余的n-k个元素reverse(nums, k, n - 1);}// 辅助函数：翻转数组的指定部分private void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}
}

5.3 代码详解

数组翻转法的优雅之处在于它非常直观：

// 1. 翻转整个数组
reverse(nums, 0, n - 1);

• 首先将整个数组翻转，这样原来的顺序就变成了逆序
• 例如：[1,2,3,4,5,6,7] 变成 [7,6,5,4,3,2,1]

// 2. 翻转前k个元素
reverse(nums, 0, k - 1);

• 然后翻转前k个元素，将这部分恢复正确的相对顺序
• 对于k=3，[7,6,5,4,3,2,1] 的前k个元素 [7,6,5] 翻转后变成 [5,6,7,4,3,2,1]

// 3. 翻转剩余的n-k个元素
reverse(nums, k, n - 1);

• 最后翻转剩余的n-k个元素，将这部分也恢复正确的相对顺序
• [5,6,7,4,3,2,1] 的后n-k个元素 [4,3,2,1] 翻转后变成 [5,6,7,1,2,3,4]
• 这就是最终的轮转结果

// 辅助函数：翻转数组的指定部分
private void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}
}

• 辅助函数实现了数组特定范围内的翻转
• 使用双指针法，从两端向中间逐步交换元素
• 这是一个标准的数组翻转操作

5.4 数学证明

为什么数组翻转法能实现轮转效果？我们可以从数学角度证明：

设原数组为A，长度为n，需要右移k个位置。

1. 定义A’ = A[0…n-k-1]，表示原数组的前n-k个元素
2. 定义A’’ = A[n-k…n-1]，表示原数组的后k个元素
3. 原数组可表示为：A = [A’, A’']
4. 向右轮转k个位置后的数组为：B = [A’‘, A’]

数组翻转法的步骤：

1. 翻转整个数组：[A’, A’‘] → [(A’‘)^r, (A’)^r]，其中r表示翻转
2. 翻转前k个元素：[(A’‘)^r, (A’)^r] → [A’‘, (A’)^r]
3. 翻转后n-k个元素：[A’‘, (A’)^r] → [A’‘, A’]

最终结果：[A’‘, A’]，这正是轮转后的结果。

5.5 复杂度分析

• 时间复杂度: O(n)，翻转数组需要O(n)的时间。
• 空间复杂度: O(1)，只使用了有限的临时变量。

5.6 适用场景

数组翻转法因其简洁性和效率，几乎适用于所有场景：

• 需要原地操作的场景
• 性能要求高的场景
• 代码简洁度要求高的场景

6. 详细步骤分析与示例跟踪

让我们通过一个具体例子来跟踪每种算法的执行过程，加深理解。

6.1 示例跟踪：使用额外数组法

输入：nums = [1,2,3,4,5,6,7], k = 3

1. 计算实际轮转次数：k = k % n = 3 % 7 = 3
2. 创建新数组：result = new int[7]
3. 将原数组元素放入新数组：
   • nums[0]=1 → result[(0+3)%7]=result[3]=1
   • nums[1]=2 → result[(1+3)%7]=result[4]=2
   • nums[2]=3 → result[(2+3)%7]=result[5]=3
   • nums[3]=4 → result[(3+3)%7]=result[6]=4
   • nums[4]=5 → result[(4+3)%7]=result[0]=5
   • nums[5]=6 → result[(5+3)%7]=result[1]=6
   • nums[6]=7 → result[(6+3)%7]=result[2]=7
4. 现在result=[5,6,7,1,2,3,4]
5. 将result复制回nums：nums=[5,6,7,1,2,3,4]

6.2 示例跟踪：环状替换法

输入：nums = [1,2,3,4,5,6,7], k = 3

1. 计算实际轮转次数：k = k % n = 3 % 7 = 3

2. 开始从start=0处的环状替换：

   • 当前位置current=0，当前值prev=nums[0]=1
   • 下一个位置next=(0+3)%7=3，保存nums[3]=4
   • 将1放入位置3：nums=[1,2,3,1,5,6,7]，current=3，prev=4
   • 下一个位置next=(3+3)%7=6，保存nums[6]=7
   • 将4放入位置6：nums=[1,2,3,1,5,6,4]，current=6，prev=7
   • 下一个位置next=(6+3)%7=2，保存nums[2]=3
   • 将7放入位置2：nums=[1,2,7,1,5,6,4]，current=2，prev=3
   • 下一个位置next=(2+3)%7=5，保存nums[5]=6
   • 将3放入位置5：nums=[1,2,7,1,5,3,4]，current=5，prev=6
   • 下一个位置next=(5+3)%7=1，保存nums[1]=2
   • 将6放入位置1：nums=[1,6,7,1,5,3,4]，current=1，prev=2
   • 下一个位置next=(1+3)%7=4，保存nums[4]=5
   • 将2放入位置4：nums=[1,6,7,1,2,3,4]，current=4，prev=5
   • 下一个位置next=(4+3)%7=0，保存nums[0]=1
   • 将5放入位置0：nums=[5,6,7,1,2,3,4]，current=0，prev=1
   • 现在current=0=start，一个循环结束，且count=7，所有元素都已处理

3. 最终结果：nums=[5,6,7,1,2,3,4]

6.3 示例跟踪：数组翻转法

输入：nums = [1,2,3,4,5,6,7], k = 3

1. 计算实际轮转次数：k = k % n = 3 % 7 = 3
2. 翻转整个数组：
   • nums=[1,2,3,4,5,6,7] → nums=[7,6,5,4,3,2,1]
3. 翻转前k个元素（前3个）：
   • nums=[7,6,5,4,3,2,1] → nums=[5,6,7,4,3,2,1]
4. 翻转剩余n-k个元素（后4个）：
   • nums=[5,6,7,4,3,2,1] → nums=[5,6,7,1,2,3,4]
5. 最终结果：nums=[5,6,7,1,2,3,4]

7. 常见错误与优化

7.1 常见错误

1. 忘记处理k大于数组长度的情况：

   // 错误：不处理k大于数组长度的情况
   public void rotate(int[] nums, int k) {// k可能大于nums.length，未处理会导致索引越界...
   }// 正确：进行取模操作
   public void rotate(int[] nums, int k) {int n = nums.length;k = k % n; // 确保k在有效范围内...
   }
   

2. 环状替换中的循环处理错误：

   // 错误：处理不完整，可能漏掉某些元素
   public void rotate(int[] nums, int k) {// ...int start = 0;int current = start;int prev = nums[start];// 只进行一个循环，可能无法处理所有元素do {// ...} while (start != current);
   }// 正确：确保处理所有元素
   public void rotate(int[] nums, int k) {// ...int count = 0;for (int start = 0; count < n; start++) {// 确保所有元素都被处理// ...count++;}
   }
   

3. 数组翻转边界错误：

   // 错误：翻转边界不正确
   reverse(nums, 0, k); // 错误，应该是k-1
   reverse(nums, k, n); // 错误，应该是k到n-1// 正确：正确的翻转边界
   reverse(nums, 0, k - 1);
   reverse(nums, k, n - 1);
   

7.2 优化技巧

1. 提前检查特殊情况：

   // 优化：提前处理不需要轮转的情况
   if (k == 0 || k % n == 0) {return; // 不需要轮转
   }
   

2. 使用Java内置的数组复制方法：

   // 优化：使用System.arraycopy替代手动循环复制
   System.arraycopy(result, 0, nums, 0, n);
   

3. 减少不必要的取模操作：

   // 优化前：每次都进行取模
   for (int i = 0; i < n; i++) {result[(i + k) % n] = nums[i];
   }// 优化后：预计算起始位置
   int start = n - k;
   for (int i = 0; i < k; i++) {result[i] = nums[start + i];
   }
   for (int i = 0; i < n - k; i++) {result[k + i] = nums[i];
   }
   

4. 环状替换中优化循环判断：

   // 优化：使用数学方法计算循环次数
   int gcd = gcd(n, k); // 计算n和k的最大公约数// 只需要进行gcd次循环，每次处理n/gcd个元素
   for (int start = 0; start < gcd; start++) {// ...
   }// 辅助方法：计算最大公约数
   private int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
   }
   

8. 三种解法的对比与选择

解法	时间复杂度	空间复杂度	优点	缺点	适用场景
额外数组法	O(n)	O(n)	简单直观，容易实现	需要额外空间	初学者，空间不敏感的场景
环状替换法	O(n)	O(1)	不需要额外空间	实现较复杂，需要处理循环	空间敏感场景，追求原地操作
数组翻转法	O(n)	O(1)	优雅简洁，不需要额外空间	需要理解翻转原理	几乎所有场景的最优选择

总结：

• 如果你是初学者或追求代码简洁性，使用额外数组法
• 如果你需要节省空间且追求性能，使用数组翻转法
• 环状替换法虽然有趣，但实现复杂，通常不是首选

9. 扩展题目与应用

9.1. 左轮转数组

与本题类似，但方向相反，将数组元素向左移动k个位置。

解决方案：

• 向左轮转k个位置等同于向右轮转n-k个位置
• 或者使用相同的数组翻转法，只需调整翻转顺序：
  1. 翻转整个数组
  2. 翻转前n-k个元素
  3. 翻转后k个元素

9.2. 字符串轮转

LeetCode 796. 旋转字符串：检查一个字符串是否可以通过多次轮转变成另一个字符串。

解决思路：将原字符串与自身拼接，如果目标字符串是拼接结果的子串，则可以通过轮转得到。

9.3. 循环移位操作

在计算机系统中，轮转操作常用于循环移位（Circular Shift）：

• 循环左移：将二进制数的最高位移到最低位
• 循环右移：将二进制数的最低位移到最高位

10. 实际应用场景

轮转数组在实际编程中有多种应用：

1. 缓冲区管理：

   • 实现循环缓冲区时，可以使用轮转数组避免数据移动
   • 在流媒体处理中保持最近的数据片段

2. 图像处理：

   • 图像旋转和变换
   • 图像滤波器的实现

3. 信号处理：

   • 信号采样和处理时的数据轮转
   • FFT算法中的数据重排

4. 游戏开发：

   • 游戏地图的循环移动（如无限地图）
   • 轮流游戏中的玩家顺序管理

5. 调度算法：

   • 轮转调度算法（Round Robin）中任务的轮换
   • 分时系统中的时间片分配

11. 完整的 Java 解决方案

以下是结合了各种最佳实践的最优解法（数组翻转法）：

class Solution {public void rotate(int[] nums, int k) {if (nums == null || nums.length <= 1) {return; // 处理边界情况}int n = nums.length;k = k % n; // 处理k大于数组长度的情况if (k == 0) {return; // 不需要轮转}// 三步翻转法reverse(nums, 0, n - 1);   // 翻转整个数组reverse(nums, 0, k - 1);   // 翻转前k个元素reverse(nums, k, n - 1);   // 翻转剩余的n-k个元素}// 翻转数组的指定范围private void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start++] = nums[end];nums[end--] = temp;}}
}

这个解法简洁高效，适用于大多数场景。在LeetCode上，这个解法通常能击败95%以上的提交。

12. 总结与技巧

12.1 解题要点

1. 正确理解轮转：理解轮转的本质是循环移动，超出数组末尾的元素会回到开头。
2. 取模处理：使用k % n来处理k可能大于数组长度的情况。
3. 选择合适的算法：根据空间要求选择适当的算法（额外空间法或原地算法）。
4. 翻转技巧：数组翻转是解决轮转问题的强大工具。

12.2 学习收获

通过学习轮转数组问题，你可以掌握：

• 原地算法的思想和实现
• 双指针技术在数组操作中的应用
• 数学思维在算法设计中的重要性
• 空间和时间复杂度的权衡

12.3 面试技巧

如果在面试中遇到此类问题：

1. 先提出最简单的解法（使用额外数组）
2. 然后提出原地算法（如数组翻转法）
3. 讨论每种方法的时间和空间复杂度
4. 分析各种解法的适用场景和优缺点
5. 实现你认为最优的解法

记住，展示你的思考过程和对不同解法的理解，比仅仅给出一个正确答案更重要。

13. 参考资料

• LeetCode 官方题解：轮转数组
• LeetCode 题目链接：轮转数组