Leetcode189:轮转数组

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：额外数组辅助 思路 使用一个额外的数组 temp 来保存最终的旋转结果。拷贝操作： 遍历原数组，将 nums[i] 放置到新位置 (i + k) % n 中。 覆盖结果： 将 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：环状替换 思路 核心观察： 通过旋转，数组中的每个元素其实沿着环状路径被移动，例如第 i 个元素移动到位置 (i + k) % n。从某个点出发，将该点开始的所有元素按照这种环状方式重新排列。当访问过的元素数量达到数组大小 n 时，正好完成所有元素的轮转。 实现步骤： 统计当前访问过的元素数量 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 步：翻转整个数组；第 2 步：翻转前 k 个元素；第 3 步：翻转后 n-k 个元素。 实现原理： 经过数组翻转操作后，元素将被正确排列。例如：对于输入 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？ 优先选择三步翻转解法：O(n) 时间复杂度，O(1) 空间复杂度，实现简单，效率最高，是面试中优先推荐的解法。针对特殊场景： 如果原数组不可修改，可以选择额外数组解法。如果需要一定技巧性（如比特运算分析竞赛题），环状替换法更具逻辑挑战。 边界情况注意： k 大于数组长度时，需要取模：k %= n。空数组或 k=0 时，直接返回。

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