当前位置：首页 > news >正文

LeetCode 189 轮转数组：三次反转原地解决，图解 Java 实现

news 2026/8/3 6:39:55

在数组题中，“轮转数组”是一道很典型的题。它的代码并不长，但同时考查了数组下标、空间复杂度、边界处理，以及能否从结果反推出操作过程。

这篇文章用 Java 解决 LeetCode 189「轮转数组」，重点讲清楚一个看起来有些巧妙的方法：为什么只需要三次反转，就能把数组向右轮转k个位置。

一、题目描述

给定一个整数数组nums，将数组中的元素向右轮转k个位置，要求直接修改原数组。

例如：

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

向右轮转 3 个位置，可以理解为：把数组末尾的 3 个元素[5,6,7]移到数组开头，其余元素[1,2,3,4]整体向后移动。

二、最容易想到的做法：使用额外数组

原数组下标为i的元素，轮转后会出现在：

(i + k) % n

因此，可以创建一个长度相同的新数组，把每个元素放入新位置，再复制回原数组：

public void rotate(int[] nums, int k) { int n = nums.length; k %= n; int[] temp = new int[n]; for (int i = 0; i < n; i++) { temp[(i + k) % n] = nums[i]; } System.arraycopy(temp, 0, nums, 0, n); }

这个方法很直观，时间复杂度为O(n)，但需要O(n)的额外空间。如果面试官进一步要求空间复杂度为O(1)，就需要考虑原地操作。

三、最优解：三次反转

仍然以数组为例：

[1, 2, 3, 4, 5, 6, 7]

向右轮转 3 位后，希望得到：

[5, 6, 7, 1, 2, 3, 4]

可以把原数组分成两部分：

A = [1, 2, 3, 4] B = [5, 6, 7]

轮转的目标，本质上就是把A + B变成B + A。

具体分三步。

第一步：反转整个数组

[1, 2, 3, 4, 5, 6, 7] ↓ [7, 6, 5, 4, 3, 2, 1]

此时两部分的位置已经交换，但每个部分内部的顺序也被反转了。可以表示为：

reverse(B) + reverse(A)

第二步：反转前 k 个元素

前 3 个元素是[7,6,5]，将其反转：

[7, 6, 5, 4, 3, 2, 1] ↓ [5, 6, 7, 4, 3, 2, 1]

这样，原数组末尾的B已经恢复成正确顺序。

第三步：反转剩余元素

再把下标k到n - 1的部分[4,3,2,1]反转：

[5, 6, 7, 4, 3, 2, 1] ↓ [5, 6, 7, 1, 2, 3, 4]

最终得到目标结果。

整个过程可以概括为：

整体反转 → 反转前 k 个元素 → 反转后 n-k 个元素

四、为什么三次反转一定成立？

假设原数组由两部分组成：

A + B

其中B是需要移到前面的最后k个元素。

第一次整体反转后得到：

reverse(B) + reverse(A)

然后分别反转前后两部分：

B + A

这正是向右轮转后的结果。因此，三次反转不是只对某个示例有效，而是对任意数组都成立。

五、完整 Java 代码

class Solution { public void rotate(int[] nums, int k) { int n = nums.length; k %= n; // 1. 反转整个数组 reverse(nums, 0, n - 1); // 2. 反转前 k 个元素 reverse(nums, 0, k - 1); // 3. 反转剩余元素 reverse(nums, k, n - 1); } private void reverse(int[] nums, int left, int right) { while (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } }

reverse方法使用双指针：left从左向右移动，right从右向左移动，每次交换两个位置的元素，直到两个指针相遇。