力扣（轮转数组）

轮转数组——三次反转法与额外数组法全解析

一、题目剖析

给定整数数组 nums 和非负整数 k，需将数组元素向右轮转 k 个位置 。比如 nums = [1,2,3,4,5,6,7]，k = 3 时，输出 [5,6,7,1,2,3,4] 。核心是原地修改数组，高效实现轮转，还要考虑 k 大于数组长度的情况（如数组长度为 5，k = 7，实际等效于 k = 2 ，需先对 k 取模优化 ）。

二、三次反转法思路拆解

（一）算法核心逻辑

利用“反转”操作的特性，通过三次反转达成轮转效果，无需额外开辟大量存储空间（空间复杂度 O(1) ）。步骤如下：

1. 整体反转：将原数组全部元素反转。比如原数组 [1,2,3,4,5,6,7]，整体反转后变为 [7,6,5,4,3,2,1] 。这一步把原本要“轮转出去”的末尾 k 个元素，移到了数组前面区域，为后续拆分做准备。
2. 前 k 个元素反转：对反转后的数组，取前 k 个元素再次反转。以上面例子，k = 3 ，前 3 个元素 [7,6,5] 反转后变回 [5,6,7] ，此时数组变为 [5,6,7,4,3,2,1] 。这一步让原本末尾的 k 个元素，以正确顺序排列在数组前端。
3. 剩余元素反转：对数组中除前 k 个元素外的部分反转。例子中剩余元素 [4,3,2,1] 反转后成为 [1,2,3,4] ，最终数组 [5,6,7,1,2,3,4] ，完成轮转。

（二）代码实现与细节

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;// 处理k过大情况，取模后减少无效轮转，比如n=5，k=7，实际只需轮转2次k = k % n; // 三次反转操作reverse(nums, 0, n - 1);     reverse(nums, 0, k - 1);     reverse(nums, k, n - 1);     }// 辅助反转方法，交换数组start到end位置的元素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--;}}
}

• k = k % n：关键优化点。因为数组长度为 n ，轮转 n 次会回到原状态，所以取模后 k 范围限定在 [0, n - 1] ，避免重复、无效的轮转操作，提升效率。
• reverse 方法**：通过双指针（start 和 end ），从数组两端向中间遍历，交换对应位置元素，实现区间反转，时间复杂度 O(m)（m 是区间长度 ），简单高效。

三、额外数组法深度解析

（一）算法核心逻辑

新建一个与原数组等长的数组，依据轮转规则，把原数组元素按新位置映射关系，逐个放到新数组对应位置，最后将新数组内容“拷贝”回原数组，达成轮转效果。核心是利用 (i + k) % n 公式确定元素新位置（i 为原数组索引，n 为数组长度 ）。比如原数组索引 i 的元素，轮转 k 次后，在新数组位置是 (i + k) % n 。

（二）代码实现与细节

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n; // 同样先处理k过大情况，减少无效操作int[] newNums = new int[n]; // 新建与原数组等长的数组for (int i = 0; i < n; i++) {// 计算原数组元素i轮转k次后的新位置int newIndex = (i + k) % n; newNums[newIndex] = nums[i]; }// 将新数组内容拷贝回原数组，完成原地修改（题目要求原地，这里通过拷贝实现）System.arraycopy(newNums, 0, nums, 0, n); }
}

• new int[] newNums = new int[n]：开辟额外 O(n) 空间存储轮转后结果，是空间复杂度为 O(n) 的关键原因。
• System.arraycopy：Java 中高效的数组拷贝方法，把新数组内容复制回原数组，满足题目“原地修改”要求（虽借助额外数组，但最终修改了原数组 ）。

四、两种算法复杂度对比分析

（一）时间复杂度

• 三次反转法：三次反转操作，每次反转时间复杂度取决于处理元素数量。整体反转 n 个元素、前 k 个反转 k 个、剩余反转 n - k 个，总操作次数 n + k + (n - k) = 2n ，时间复杂度 O(n)（n 为数组长度 ）。
• 额外数组法：遍历原数组 n 次（赋值到新数组 ），加上数组拷贝操作（也是 O(n) ），总操作次数约 2n ，时间复杂度同样是 O(n) 。

（二）空间复杂度

• 三次反转法：仅用几个变量（n、k、start、end、temp 等 ），无额外与数组规模相关的存储空间，空间复杂度 O(1) 。
• 额外数组法：需新建长度为 n 的数组，空间复杂度 O(n) ，对内存占用大，处理极大数组时可能受限。

五、两种解法优劣与适用场景对比

比如处理百万级长度数组，三次反转法在内存使用上优势显著；若解题时追求快速编码、逻辑清晰，额外数组法更合适（尤其面试中，短时间想不出反转技巧时，该方法易实现 ）。

六、总结与拓展

三次反转法以“逆向思维 + 分步操作”，用极小空间成本解决数组轮转问题，是算法设计中“巧妙组合基础操作”的典范；额外数组法凭借直观逻辑，成为理解轮转问题的“入门级”解法。

两种方法展现了不同解题思路——前者追求极致空间优化，后者注重逻辑简洁。在实际开发或算法题中，可根据数据规模、空间限制、代码可读性要求灵活选择。同时，这类“数组变形”题的解题思路，还可迁移到字符串循环移位（如字符串 abcd 循环右移 2 位变 cdab ，可借鉴相同逻辑 ），助力我们举一反三，提升算法思维。

掌握这两种解法，面对数组轮转类问题，就能根据场景灵活应对，既懂“高效优化”的反转技巧，也会“直观清晰”的额外数组方法，全方位提升算法解题能力