Leetcode 189: 轮转数组

Leetcode 189: 轮转数组

这是一道经典问题，题目要求将一个数组向右轮转 k 个位置，有多种解法可以快速求解，既可以通过额外空间，也可以在 O(1) 的空间复杂度内完成。本题考察数组操作、双指针，以及算法优化能力。

---

题目描述

输入：

• 一个整数数组 nums
• 一个整数 k（表示右移的次数）。

输出：

• 将数组元素旋转 k 次后直接修改原数组，不返回值。

---

示例输入输出：

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

---

解法 1：额外数组辅助

思路

1. 使用一个额外的数组 temp 来保存最终的旋转结果。
2. 拷贝操作：
   • 遍历原数组，将 nums[i] 放置到新位置 (i + k) % n 中。
3. 覆盖结果：
   • 将 temp 中的内容转存回原数组。

---

代码模板

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n; // 如果 k 大于数组长度，需要取模int[] temp = new int[n];for (int i = 0; i < n; i++) {temp[(i + k) % n] = nums[i]; // 按照旋转后的位置存储}// 将 temp 的内容拷贝到原数组for (int i = 0; i < n; i++) {nums[i] = temp[i];}}
}

---

复杂度分析

• 时间复杂度：O(n)
  • 遍历数组两次，一次构造 temp 数组，一次拷贝回原数组。
• 空间复杂度：O(n)
  • 需要一个额外大小为 n 的数组存放临时结果。

---

解法 2：环状替换

思路

1. 核心观察：
   • 通过旋转，数组中的每个元素其实沿着环状路径被移动，例如第 i 个元素移动到位置 (i + k) % n。
   • 从某个点出发，将该点开始的所有元素按照这种环状方式重新排列。
   • 当访问过的元素数量达到数组大小 n 时，正好完成所有元素的轮转。
2. 实现步骤：
   • 统计当前访问过的元素数量 count，从未访问过的某个起始点出发进行 “环绕替换”。
   • 对于每个元素，将其移至新位置 (i + k) % n，直到形成一个环，然后跳到下一个未访问的点。

---

代码模板

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n; // 如果 k 大于数组长度，取模去掉多余轮转int count = 0; // 记录访问的元素数量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; // 替换值prev = temp; // 更新 "前一个值"current = next; // 跳到下一个位置count++; // 更新访问数量} while (current != start); // 环绕回起点时退出}}
}

---

复杂度分析

• 时间复杂度：O(n)
  • 每个元素最多被访问一次。
• 空间复杂度：O(1)
  • 没有使用额外数据结构，原地旋转。

---

解法 3：数组翻转技巧

思路

1. 数组轮转可以通过 三步翻转 实现：
   • 第 1 步：翻转整个数组；
   • 第 2 步：翻转前 k 个元素；
   • 第 3 步：翻转后 n-k 个元素。
2. 实现原理：
   • 经过数组翻转操作后，元素将被正确排列。
   • 例如：对于输入 nums = [1,2,3,4,5,6,7], k=3：

     原始： [1, 2, 3, 4, 5, 6, 7]
     步骤 1 翻转整个数组： [7, 6, 5, 4, 3, 2, 1]
     步骤 2 翻转前 k 个元素：[5, 6, 7, 4, 3, 2, 1]
     步骤 3 翻转后 n-k 个元素：[5, 6, 7, 1, 2, 3, 4]
     

---

代码模板

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n; // 如果 k 大于数组长度，取模处理// 翻转函数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;start++;end--;}}
}

---

复杂度分析

• 时间复杂度：O(n)
  • 翻转整个数组花费 O(n)，翻转前后两部分各花费 O(k) 和 O(n-k)，总时间为 O(n)。
• 空间复杂度：O(1)
  • 翻转操作原地完成，没有额外数据结构。

---

解法 4：双指针 + 循环节

思路

• 使用双指针从两端到中间进行元素筛选调整。
• 或者结合环状数组的位置动态安排记录。

---

---

总结：如何快速 AC？

1. 优先选择三步翻转解法：O(n) 时间复杂度，O(1) 空间复杂度，实现简单，效率最高，是面试中优先推荐的解法。
2. 针对特殊场景：
   • 如果原数组不可修改，可以选择额外数组解法。
   • 如果需要一定技巧性（如比特运算分析竞赛题），环状替换法更具逻辑挑战。
3. 边界情况注意：
   • k 大于数组长度时，需要取模：k %= n。
   • 空数组或 k=0 时，直接返回。

通过掌握以上 3 种高效解法（特别是三步翻转技巧），不仅可以轻松解决问题，还能给面试官留下深刻印象。