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

在数组题中“轮转数组”是一道很典型的题。它的代码并不长但同时考查了数组下标、空间复杂度、边界处理以及能否从结果反推出操作过程。这篇文章用 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从右向左移动每次交换两个位置的元素直到两个指针相遇。六、为什么必须对 k 取模如果数组长度为 7而k 10向右轮转 10 次和向右轮转 3 次的结果相同10 % 7 3因为每轮转n次数组都会恢复原状所以真正有效的轮转次数是k % nums.length;这一步还能避免k大于数组长度时后续反转区间越界。当k 0时第二次反转调用的区间是[0, -1]。由于reverse中的条件是left right循环不会执行代码仍然能够正确运行。七、复杂度分析虽然进行了三次反转但每个元素只会被交换有限次因此时间复杂度O(n)空间复杂度O(1)它没有创建与数组长度相关的辅助空间满足原地修改的要求。八、常见错误1. 忘记对 k 取模当k nums.length时反转区间可能越界。进入反转逻辑前应先执行k % n。2. 反转顺序写错向右轮转的常见写法是整体 → 前 k 个 → 后 n-k 个不要把k误写成n - k。可以始终记住向右轮转后原数组最后的k个元素要出现在最前面。3. 逐个移动导致超时如果每轮转一次就把整个数组移动一遍那么时间复杂度是O(n × k)。当数组和k都很大时这种方法容易超时。4. 只修改了局部变量题目要求原地修改nums不能只让一个新数组变量指向结果而不复制回去。三次反转直接操作原数组不存在这个问题。