原地轮转数组的两种高效实现详解

轮转数组是算法中的一个经典问题，常见于面试和编程练习中。其核心目标是将数组向右轮转 k 个位置。本文将介绍两种高效的实现方案： 临时数组法和 三次反转法，帮助读者理解不同场景下的最优选择。

---

问题描述

给定一个整数数组 nums 和一个正整数 k，要求将数组向右轮转 k 个位置。例如：

• 输入：nums = [1,2,3,4,5], k = 2
• 输出：[4,5,1,2,3]

---

方法一：临时数组法

核心思路

1. 暂存后k个元素：将数组末尾的 k 个元素保存到临时数组中。
2. 平移前n-k个元素：将数组前 n-k 个元素向后移动 k 个位置。
3. 填充前k个位置：将临时数组中的元素复制到数组开头。

代码实现

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;if (n == 0 || k == 0) return;k %= n; // 处理k > n的情况// 1. 暂存后k个元素int[] temp = new int[k];for (int i = n - k, j = 0; i < n; i++) {temp[j++] = nums[i];}// 2. 平移前n-k个元素for (int m = n - 1; m >= k; m--) {nums[m] = nums[m - k];}// 3. 填充前k个位置for (int i = 0; i < k; i++) {nums[i] = temp[i];}}
}

关键步骤分析

1. 预处理k的值
   通过 k %= n 确保 k 始终小于数组长度，避免无效操作和索引越界。

2. 暂存后k个元素

   • 从索引 n-k 开始，复制 k 个元素到临时数组。
   • 示例：nums = [1,2,3,4,5], k=2 → temp = [4,5]。

3. 平移前n-k个元素

   • 从后向前移动：避免覆盖未处理的元素。
   • 示例：将 [1,2,3] 向后移动2位，得到 [1,2,1,2,3]。

4. 填充前k个位置

   • 将临时数组中的元素复制到数组开头，完成轮转。
   • 示例：填充 [4,5] → 最终结果 [4,5,1,2,3]。

复杂度分析

• 时间复杂度：( O(n) )，三次独立遍历数组。
• 空间复杂度：( O(k) )，需额外存储 k 个元素。

---

方法二：三次反转法（原地算法）

核心思路

1. 整体反转数组：将整个数组完全反转。
2. 反转前k个元素：调整前 k 个元素的顺序。
3. 反转剩余元素：调整后 n-k 个元素的顺序。

代码实现

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;if (n == 0 || k == 0) return;k %= n; // 处理k > n的情况// 三次反转操作reverse(nums, 0, n - 1); // 1. 整体反转reverse(nums, 0, k - 1); // 2. 反转前k个元素reverse(nums, k, n - 1); // 3. 反转剩余元素}// 辅助函数：反转数组指定区间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--;}}
}

关键步骤分析

1. 整体反转

   • 示例：[1,2,3,4,5] → [5,4,3,2,1]。

2. 反转前k个元素

   • 示例：反转前2个元素 → [4,5,3,2,1]。

3. 反转剩余元素

   • 示例：反转后3个元素 → [4,5,1,2,3]。

复杂度分析

• 时间复杂度：( O(n) )，三次反转操作。
• 空间复杂度：( O(1) )，仅需常数级别空间。

---

方法对比与选择建议

特性	临时数组法	三次反转法
空间复杂度	( O(k) )	( O(1) )
代码直观性	较简单	需理解反转逻辑
适用场景	内存充足，需快速实现	内存敏感，需严格原地操作

---

示例验证

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

• 临时数组法：

  1. temp = [4,5]
  2. 平移后数组 → [1,2,1,2,3]
  3. 最终结果 → [4,5,1,2,3]

• 三次反转法：

  1. 整体反转 → [5,4,3,2,1]
  2. 反转前2个 → [4,5,3,2,1]
  3. 反转剩余 → [4,5,1,2,3]

---

总结

1. 临时数组法：

   • 优点：逻辑直观，代码简单。
   • 缺点：需额外空间存储 k 个元素。

2. 三次反转法：

   • 优点：原地操作，空间最优。
   • 缺点：需熟悉反转逻辑，索引处理需谨慎。

根据实际场景选择合适的方法，若内存允许且追求代码简洁性，可选用临时数组法；若需严格原地操作，三次反转法是更优选择。