解法：从取模映射到三次反转与环形替换)
在LeetCode热题100的榜单里轮转数组Rotate Array是一道耐人寻味的题。它表面上是“数组遍历拷贝”的入门难度实际却能串起O(n)时间、O(1)空间、取模映射、环状替换、三次反转这一整条算法思维链。我刷这道题的时候第一版直接用Python切片一行AC觉得自己很厉害后来在一次模拟面试里被追问“原地修改怎么做”“环数为什么是gcd(n,k)”才发现自己只是背了个结论并没有真正掌握它。这篇文章我不打算只贴题解而是把三种O(n)解法从原理到代码再到易错点完整拆开并聊聊轮转思想在工程里的真实用法比如环形缓冲区、位点回退、JDK源码中的rotate实现。适合刚刷到热题100的新手也适合准备面试时想把数组题讲透彻的朋友。1. 先把题目吃透轮转数组到底在考什么1.1 原题回顾与第一直觉题目要求非常直白给定一个数组nums将数组中的元素向右轮转k个位置k是非负数。举个例子nums [1,2,3,4,5,6,7]k 3轮转后得到[5,6,7,1,2,3,4]。所谓“向右轮转”可以理解成每个元素都往右挪k格末尾的元素循环补到开头。大多数人看到这题的第一直觉是新建一个临时数组遍历原数组把它放到正确的位置上。这个思路没有错代码也能在LeetCode上AC时间复杂度O(n)。但如果你认真读题会发现题目的函数签名在多数语言里是void rotate(int[] nums, int k)比如Java版本明确要求原地修改数组不返回新数组。这就意味着直接return newArray是过不了编译的必须真实改动传入的数组内容。所以这道题在考一个非常基础但容易被忽略的东西你知不知道“原数组必须被修改”和“你只是创建了一个新的局部变量”之间的区别。很多新手在这个细节上栽跟头Python里nums nums[-k:] nums[:-k]并不会修改原数组必须写成nums[:] ...这就是第一个隐藏的考点。1.2 三个容易被忽视的前提条件轮转数组看着简单但有三个条件会直接决定你的解法能不能通过必须提前确认。第一k可能大于数组长度。LeetCode并没有限制k必须小于n比如n7k23实际轮转效果等同于k23%72。如果不对k取模前两个解法都会数组越界三次反转法更是会直接乱套。所以任何解法第一步都应当是k % nums.length这既是正确性要求也是后续计算的简化前提。第二空间限制。题目没有明确说“不得使用额外空间”但面试中几乎必问“能不能O(1)空间”。额外数组法是O(n)空间在某些严格场景下不可接受。轮转数组的价值就在于此是否存在一个既保持O(n)时间又做到O(1)空间的原地算法答案是肯定的而且不止一种这就是三次反转和环形替换登场的理由。第三方向语义。“向右轮转”带环状语义元素从尾部绕回头部。对于长度为n的数组向右轮转k位等价于向左轮转(n-k)位。有些衍生题目会考左旋字符串比如剑指Offer的“左旋转字符串”本质和这题互为镜像理解了方向就不会被变体难住。这三个条件搞不清楚刷题就只是“照着题解抄一遍”换个顺序换个参数立刻露馅。这也是为什么轮转数组能进热题100它是数组题里最典型的“细节里见功底”的题目。2. 三种O(n)解法从直观到最优2.1 解法一额外数组映射最直观的O(n)解法额外数组法的核心逻辑一句话讲完新数组下标为(i k) % n的位置应当存放原数组下标为i的元素。代码如下public void rotate(int[] nums, int k) { int n nums.length; k % n; int[] newArr new int[n]; for (int i 0; i n; i) { newArr[(i k) % n] nums[i]; } System.arraycopy(newArr, 0, nums, 0, n); }这个解法的正确性来源于“轮转”的数学本质每个元素的位置都发生了一次固定的偏移量相加。取模是为了处理越界回卷(i k) % n就是轮转后的位置。之所以要先对k取模是因为如果k n 2轮转效果和k 2一样取模后计算量更小、也不会产生越界。时间复杂度O(n)没得说遍历一次数组完成放置再遍历一次拷贝回来。空间复杂度O(n)因为newArr和nums长度一样。严格说它并不满足“原地修改”的精神内核但在LeetCode的判题规则里只要最后用System.arraycopy把结果拷回原数组就算通过了题目的验证逻辑。我的建议是面试时如果直接抛这个解法需要立刻补一句“这是最简单直观的做法但空间复杂度是O(n)可以优化到O(1)”。这样既展示了你能快速给出可运行方案又表明你有优化意识。但光给出这一版不够后面两个才是真正的加分点。2.2 解法二三次反转O(1)空间的标准答案三次反转法也叫“翻手法”是轮转数组在面试中最受欢迎的解法。它的原理可以从“段交换”的角度理解向右轮转k位本质上是把数组的最后k个元素整体搬到前面而前面的n-k个元素整体平移到后面。如果我们把数组看成两段——A段是前n-k个元素B段是后k个元素——那么轮转的结果就是从A B变成B A。如何在不借助额外数组的前提下完成“两段交换”一个优美的结论是对整串先反转再分别反转两段。以nums [1,2,3,4,5,6,7]k 3为例第一步反转整个数组得到[7,6,5,4,3,2,1] 第二步反转前k个元素也就是下标0到2得到[5,6,7,4,3,2,1] 第三步反转后n-k个元素也就是下标3到6得到[5,6,7,1,2,3,4]。三步结束结果正是轮转后的数组。整个过程只用了常数级额外空间时间复杂度依然是O(n)因为每次反转都需要线性遍历被反转的区间。代码实现也不复杂public void rotate(int[] nums, int k) { int n nums.length; k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); 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--; } }注意一个细节如果k先取模后等于0三个reverse操作会变成reverse(0, n-1)、reverse(0, -1)、reverse(n, n-1)。第二个和第三个反转的区间分别是空区间reverse方法里的left right条件会直接跳过不会出问题。但如果你在reverse里用了数组下标访问而没有先判断空区间k0时会直接越界。这也是为什么我习惯把所有边界都写在方法内部的while判断里而不是在调用方做条件判断。三次反转法的正确性证明可以从数学归纳或直接观察入手第一次全反转把元素顺序彻底颠倒第二次反转前k个把它们恢复成正确的原顺序第三次反转后n-k个也恢复成正确的原顺序。因为轮转后的数组就是“原数组的后k个保持顺序前n-k个保持顺序”三次反转恰好把这两个段分别“翻转两次”恢复了顺序。Python版本的实现同样简洁注意切片写法不算原地这里给出真正的swap版def rotate(self, nums: List[int], k: int) - None: n len(nums) k % n def reverse(i: int, j: int) - None: while i j: nums[i], nums[j] nums[j], nums[i] i 1 j - 1 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)2.3 解法三环形替换数学思维拉满的O(n)解法如果说三次反转是“巧”环形替换Cyclic Replacement就是“数学”。这种解法的思路是元素从位置i移动到位置(i k) % n如果不做额外拷贝就必须用“链式替换”的方式不断往下推。从某个起点start开始把nums[start]保存为prev然后计算start的下一站next (start k) % n。把nums[next]保存为temp把prev放到nums[next]的位置然后继续以next为当前下标、temp为新的prev继续循环下去。当next再次回到start时这个环就走完了。一个环走完不代表所有元素都归位了。比如n 6k 2从0出发依次经过0、2、4、0只覆盖了下标0、2、4下标1、3、5还没有动需要从start 1再起一个环。所以需要外层循环来枚举起点同时用一个计数器count记录已经放置了多少个元素。一旦count n说明所有位置都处理完毕可以停止。public void rotate(int[] nums, int k) { int n nums.length; k % n; if (k 0) return; int count 0; for (int start 0; count n; start) { int cur start; int prev nums[start]; do { int next (cur k) % n; int temp nums[next]; nums[next] prev; prev temp; cur next; count; } while (cur ! start); } }这里有一个容易翻车的地方为什么外部循环起点可以朴素地写成start因为count n这个条件保证循环一定会在所有元素被安置后退出。即使某些起点对应的环已经被之前的环走过了它们的do-while至少会执行一次然后立刻回到起点count也不会有问题只是多走了一个原地环。更严谨的写法是通过gcd(n, k)控制环的数量但用count计数是最省心的方式避免了计算gcd的额外分支。从数学上讲环的个数等于gcd(n, k)。为什么从0出发每走一步下标增加k走到第t步回到0的条件是t * k是n的倍数。最小的正t是n / gcd(n, k)这就是单环长度。总元素数n除以单环长度n / gcd(n, k)得到环数正好是gcd(n, k)。如果你想严格按环数来做外层循环可以写成int cycles gcd(n, k); for (int start 0; start cycles; start) { // ... do-while }但count版本更简洁也更不容易算错gcd边界。环形替换的时间复杂度是O(n)因为每个元素恰好被放置一次空间O(1)。它的交换次数和三次反转不同三次反转每次reverse是两两交换三次反转总交换次数大约n/2 k/2 (n-k)/2 n次环形替换则是n次赋值加n次临时保存。实际执行时间差距很小但环形替换的写法更容易被面试官追问“为什么不会死循环”“环的数量怎么推导”能讲清楚就是明显加分。三种解法放在一起复杂度对比如下解法时间复杂度空间复杂度原地修改实现难度额外数组映射O(n)O(n)否低三次反转O(n)O(1)是中环形替换O(n)O(1)是高3. 实操验证从本地调到LeetCode提交3.1 构造测试用例把边界全打一遍刷题最忌讳“只跑题目的示例”。轮转数组这道题的边界条件相当多我建议本地至少准备这么一组用例用例输入k期望输出考察点普通用例[1,2,3,4,5,6,7]3[5,6,7,1,2,3,4]基本正确性k大于n[1,2,3,4,5,6]8[5,6,1,2,3,4]取模k等于n[1,2,3,4]4[1,2,3,4]取模后为0k等于0[1,2,3,4]0[1,2,3,4]不做任何操作单元素数组[5]5[5]长度1时任何操作都无意义空数组[]3[]注意n0时取模要先判断n与k互质[1,2,3,4,5]2[4,5,1,2,3]环形替换单环覆盖全部n与k不互质[1,2,3,4,5,6]2[5,6,1,2,3,4]环形替换多环尤其注意空数组的情况k % n在n0时会抛出除零异常所以要先判断if (nums null || nums.length 0) return;。LeetCode的测试用例未必覆盖到你但本地验证和面试手写时这就是隐藏扣分点。3.2 本地搭建最小验证环境我用Java演示其实任何语言都一样。把三种解法封装到同一个类里再用main方法跑断言中间可以打印每次反转/替换后的数组方便观察过程是否正确。public class RotateArrayDemo { public static void main(String[] args) { int[] nums1 {1, 2, 3, 4, 5, 6, 7}; rotateByReverse(nums1, 3); System.out.println(Arrays.toString(nums1)); // 期望 [5, 6, 7, 1, 2, 3, 4] int[] nums2 {1, 2, 3, 4, 5, 6}; rotateByCycle(nums2, 2); System.out.println(Arrays.toString(nums2)); // 期望 [5, 6, 1, 2, 3, 4] } public static void rotateByReverse(int[] nums, int k) { int n nums.length; if (n 0) return; k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } public static void rotateByCycle(int[] nums, int k) { int n nums.length; if (n 0) return; k % n; if (k 0) return; int count 0; for (int start 0; count n; start) { int cur start; int prev nums[start]; do { int next (cur k) % n; int temp nums[next]; nums[next] prev; prev temp; cur next; count; } while (cur ! start); } } private static void reverse(int[] nums, int i, int j) { while (i j) { int t nums[i]; nums[i] nums[j]; nums[j] t; i; j--; } } }在本地跑这种demo的好处是可以随手加打印语句观察每一步结果。我第一次调环形替换时就是靠打印发现count没有加在正确位置导致明明环已经走完但仍然死循环。调试器断点固然可以用但对数组下标循环这种场景打印中间态往往更快。3.3 提交时常见的几个失误最典型的失误是Python切片写法没加nums[:] 直接写nums ...。这会导致函数内部创建了一个新的局部列表原数组纹丝不动LeetCode判题直接报错。其次是把返回类型搞错比如Java版本写出public int[] rotate改了签名自然编译不过。第三个失误是三次反转法的区间写错。比如把第二次反转写成reverse(nums, 0, k)多转了一个元素或者第三次反转写成reverse(nums, k 1, n - 1)漏掉一个元素。这些边界在k3、n7的用例下不一定立刻看出来但用k1、n2这种极小用例一跑就原形毕露。我的习惯是写一个通用的reverse方法之后每次都从边界用例先验证。第四个失误发生在环形替换里把do-while误写成while导致第一个起点位置对应的环没有执行替换就直接退出因为cur初始等于start。环形替换必须保证“至少走一步”所以至少用do-while或者在while之前手动执行一次。4. 工程实践轮转思想在真实项目里的应用4.1 环形缓冲区与滚动窗口轮转数组不只是面试题它背后对应着计算机系统里无处不在的“环形”思维。最常见的工程案例就是环形队列底层用固定长度数组维护一个head指针和当前长度出队入队时用(head offset) % capacity定位元素。当你需要把整个缓冲区的内容“回退”或者“前移”若干步时本质上就是做一次轮转操作。比如音视频播放器里的音频环形缓冲区写入端不断把数据追加到写指针位置读取端从读指针消费数据。如果播放器支持seek拖动进度条需要把读指针向后移动这等价于把缓冲区的有效数据段“轮转”到新的起点。虽然实际代码里不会真的物理移动数组元素而是直接移动指针但理解的数学模型和轮转数组完全一致位置加上一个偏移量然后对长度取模。另一个场景是滑动窗口中的“滚动日志”。运维系统里常见的日志滚动log rotation是删除旧文件、创建新文件属于广义的“旋转”。如果把整个日志列表看成数组按时间周期滚动输出同样符合轮转的语义。4.2 从JDK标准库看轮转的工程实现很多语言的标准库已经内置了轮转操作研究它们的实现比死背题解更有价值。Java的java.util.Collections类里有个rotate(List? list, int distance)方法底层实现就是今天说的三次反转思路。JDK源码的逻辑大致是如果list支持RandomAccess比如ArrayList就分别反转两个区间size小的时候还会用更省事的“交换整段”的算法。本质上Collections.rotate就是把[0, n-distance)和[n-distance, n)两段互换位置。Python里没有直接的list.rotate方法但可以用切片nums[:] nums[-k:] nums[:-k]语法上非常优雅代价是O(n)空间。如果要求原地且O(1)空间就回到上面的三次反转。工程上如果代码可读性优先、且数据量不大直接用切片完全没问题但当你处理的是大数组、内嵌在性能敏感路径上时两次反转比切片少分配一个大对象GC压力更小。从这个角度看刷题学到的三种解法并非纸上谈兵标准库作者早就把高频套路写成了官方实现我们手写一遍等于理解了“为什么标准库要这么写”。4.3 位点回退与循环分页在消息队列的消费场景中位点offset回退是一个很实际的操作。消费者组误处理了一批消息想要从更早的位点重新消费本质上就是把当前消费指针向前回退。如果各位点是顺序整数回退就是“下标减去偏移量再对消息总数取模”。一个完整的“从头再来”相当于把消息序列轮转了一圈。循环分页也用到取模下标的惯用法。比如某些业务要求“无限滚动分页”第一页的下一页永远存在每页大小固定页号对总量取模。这种场景的底层计算和(i k) % n如出一辙只是把“数组”换成了“数据库主键列表”。掌握轮转数组等于掌握了这类循环取模下标的基础模型。5. 从这道题延伸出的思考刷题与工程的平衡轮转数组被收录进热题100不只是因为它简单而是因为它能牵出一整片知识网络。三次反转法在“反转单词顺序”“矩阵旋转90度”里会被反复用到环形替换法的gcd推导在“链表环检测”“循环数组相关题目”里也有影子额外数组法虽然空间不是最优但它是“空间换时间”思维的典型例子。把这三条线串起来比背下这一道题的价值大得多。面试的时候我的建议是先给出额外数组映射作为baseline再用“能否优化空间复杂度”这句话引出三次反转。如果面试官深入追问再拿出环形替换并把gcd(n, k)的推导过程讲出来。这种层层递进的节奏体现的不是“背题”而是“理解题目空间”。我自己在实际面试中遇到过几次追问几乎都集中在环形替换的退出条件上。很多人代码能写对但说不清为什么用count说不清环的数量为什么是gcd。建议你在刷完这道题后手动推导n7、k3和n6、k2这两个例子一个环覆盖全部一个分成两个环亲身验证一次比看十遍题解都管用。最后再分享一个小技巧如果你想检验自己是不是真懂了轮转数组可以试着把题目改一下——向左轮转k位、原地翻转整个数组再轮转、在链表中实现同样的轮转。每一个变体都跑一遍你会发现核心不离取模、分段反转和环状替换这三板斧。到那个时候这道题才真正从“做过”变成了“会做”。
在LeetCode热题100的榜单里轮转数组Rotate Array是一道耐人寻味的题。它表面上是“数组遍历拷贝”的入门难度实际却能串起O(n)时间、O(1)空间、取模映射、环状替换、三次反转这一整条算法思维链。我刷这道题的时候第一版直接用Python切片一行AC觉得自己很厉害后来在一次模拟面试里被追问“原地修改怎么做”“环数为什么是gcd(n,k)”才发现自己只是背了个结论并没有真正掌握它。这篇文章我不打算只贴题解而是把三种O(n)解法从原理到代码再到易错点完整拆开并聊聊轮转思想在工程里的真实用法比如环形缓冲区、位点回退、JDK源码中的rotate实现。适合刚刷到热题100的新手也适合准备面试时想把数组题讲透彻的朋友。1. 先把题目吃透轮转数组到底在考什么1.1 原题回顾与第一直觉题目要求非常直白给定一个数组nums将数组中的元素向右轮转k个位置k是非负数。举个例子nums [1,2,3,4,5,6,7]k 3轮转后得到[5,6,7,1,2,3,4]。所谓“向右轮转”可以理解成每个元素都往右挪k格末尾的元素循环补到开头。大多数人看到这题的第一直觉是新建一个临时数组遍历原数组把它放到正确的位置上。这个思路没有错代码也能在LeetCode上AC时间复杂度O(n)。但如果你认真读题会发现题目的函数签名在多数语言里是void rotate(int[] nums, int k)比如Java版本明确要求原地修改数组不返回新数组。这就意味着直接return newArray是过不了编译的必须真实改动传入的数组内容。所以这道题在考一个非常基础但容易被忽略的东西你知不知道“原数组必须被修改”和“你只是创建了一个新的局部变量”之间的区别。很多新手在这个细节上栽跟头Python里nums nums[-k:] nums[:-k]并不会修改原数组必须写成nums[:] ...这就是第一个隐藏的考点。1.2 三个容易被忽视的前提条件轮转数组看着简单但有三个条件会直接决定你的解法能不能通过必须提前确认。第一k可能大于数组长度。LeetCode并没有限制k必须小于n比如n7k23实际轮转效果等同于k23%72。如果不对k取模前两个解法都会数组越界三次反转法更是会直接乱套。所以任何解法第一步都应当是k % nums.length这既是正确性要求也是后续计算的简化前提。第二空间限制。题目没有明确说“不得使用额外空间”但面试中几乎必问“能不能O(1)空间”。额外数组法是O(n)空间在某些严格场景下不可接受。轮转数组的价值就在于此是否存在一个既保持O(n)时间又做到O(1)空间的原地算法答案是肯定的而且不止一种这就是三次反转和环形替换登场的理由。第三方向语义。“向右轮转”带环状语义元素从尾部绕回头部。对于长度为n的数组向右轮转k位等价于向左轮转(n-k)位。有些衍生题目会考左旋字符串比如剑指Offer的“左旋转字符串”本质和这题互为镜像理解了方向就不会被变体难住。这三个条件搞不清楚刷题就只是“照着题解抄一遍”换个顺序换个参数立刻露馅。这也是为什么轮转数组能进热题100它是数组题里最典型的“细节里见功底”的题目。2. 三种O(n)解法从直观到最优2.1 解法一额外数组映射最直观的O(n)解法额外数组法的核心逻辑一句话讲完新数组下标为(i k) % n的位置应当存放原数组下标为i的元素。代码如下public void rotate(int[] nums, int k) { int n nums.length; k % n; int[] newArr new int[n]; for (int i 0; i n; i) { newArr[(i k) % n] nums[i]; } System.arraycopy(newArr, 0, nums, 0, n); }这个解法的正确性来源于“轮转”的数学本质每个元素的位置都发生了一次固定的偏移量相加。取模是为了处理越界回卷(i k) % n就是轮转后的位置。之所以要先对k取模是因为如果k n 2轮转效果和k 2一样取模后计算量更小、也不会产生越界。时间复杂度O(n)没得说遍历一次数组完成放置再遍历一次拷贝回来。空间复杂度O(n)因为newArr和nums长度一样。严格说它并不满足“原地修改”的精神内核但在LeetCode的判题规则里只要最后用System.arraycopy把结果拷回原数组就算通过了题目的验证逻辑。我的建议是面试时如果直接抛这个解法需要立刻补一句“这是最简单直观的做法但空间复杂度是O(n)可以优化到O(1)”。这样既展示了你能快速给出可运行方案又表明你有优化意识。但光给出这一版不够后面两个才是真正的加分点。2.2 解法二三次反转O(1)空间的标准答案三次反转法也叫“翻手法”是轮转数组在面试中最受欢迎的解法。它的原理可以从“段交换”的角度理解向右轮转k位本质上是把数组的最后k个元素整体搬到前面而前面的n-k个元素整体平移到后面。如果我们把数组看成两段——A段是前n-k个元素B段是后k个元素——那么轮转的结果就是从A B变成B A。如何在不借助额外数组的前提下完成“两段交换”一个优美的结论是对整串先反转再分别反转两段。以nums [1,2,3,4,5,6,7]k 3为例第一步反转整个数组得到[7,6,5,4,3,2,1] 第二步反转前k个元素也就是下标0到2得到[5,6,7,4,3,2,1] 第三步反转后n-k个元素也就是下标3到6得到[5,6,7,1,2,3,4]。三步结束结果正是轮转后的数组。整个过程只用了常数级额外空间时间复杂度依然是O(n)因为每次反转都需要线性遍历被反转的区间。代码实现也不复杂public void rotate(int[] nums, int k) { int n nums.length; k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); 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--; } }注意一个细节如果k先取模后等于0三个reverse操作会变成reverse(0, n-1)、reverse(0, -1)、reverse(n, n-1)。第二个和第三个反转的区间分别是空区间reverse方法里的left right条件会直接跳过不会出问题。但如果你在reverse里用了数组下标访问而没有先判断空区间k0时会直接越界。这也是为什么我习惯把所有边界都写在方法内部的while判断里而不是在调用方做条件判断。三次反转法的正确性证明可以从数学归纳或直接观察入手第一次全反转把元素顺序彻底颠倒第二次反转前k个把它们恢复成正确的原顺序第三次反转后n-k个也恢复成正确的原顺序。因为轮转后的数组就是“原数组的后k个保持顺序前n-k个保持顺序”三次反转恰好把这两个段分别“翻转两次”恢复了顺序。Python版本的实现同样简洁注意切片写法不算原地这里给出真正的swap版def rotate(self, nums: List[int], k: int) - None: n len(nums) k % n def reverse(i: int, j: int) - None: while i j: nums[i], nums[j] nums[j], nums[i] i 1 j - 1 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)2.3 解法三环形替换数学思维拉满的O(n)解法如果说三次反转是“巧”环形替换Cyclic Replacement就是“数学”。这种解法的思路是元素从位置i移动到位置(i k) % n如果不做额外拷贝就必须用“链式替换”的方式不断往下推。从某个起点start开始把nums[start]保存为prev然后计算start的下一站next (start k) % n。把nums[next]保存为temp把prev放到nums[next]的位置然后继续以next为当前下标、temp为新的prev继续循环下去。当next再次回到start时这个环就走完了。一个环走完不代表所有元素都归位了。比如n 6k 2从0出发依次经过0、2、4、0只覆盖了下标0、2、4下标1、3、5还没有动需要从start 1再起一个环。所以需要外层循环来枚举起点同时用一个计数器count记录已经放置了多少个元素。一旦count n说明所有位置都处理完毕可以停止。public void rotate(int[] nums, int k) { int n nums.length; k % n; if (k 0) return; int count 0; for (int start 0; count n; start) { int cur start; int prev nums[start]; do { int next (cur k) % n; int temp nums[next]; nums[next] prev; prev temp; cur next; count; } while (cur ! start); } }这里有一个容易翻车的地方为什么外部循环起点可以朴素地写成start因为count n这个条件保证循环一定会在所有元素被安置后退出。即使某些起点对应的环已经被之前的环走过了它们的do-while至少会执行一次然后立刻回到起点count也不会有问题只是多走了一个原地环。更严谨的写法是通过gcd(n, k)控制环的数量但用count计数是最省心的方式避免了计算gcd的额外分支。从数学上讲环的个数等于gcd(n, k)。为什么从0出发每走一步下标增加k走到第t步回到0的条件是t * k是n的倍数。最小的正t是n / gcd(n, k)这就是单环长度。总元素数n除以单环长度n / gcd(n, k)得到环数正好是gcd(n, k)。如果你想严格按环数来做外层循环可以写成int cycles gcd(n, k); for (int start 0; start cycles; start) { // ... do-while }但count版本更简洁也更不容易算错gcd边界。环形替换的时间复杂度是O(n)因为每个元素恰好被放置一次空间O(1)。它的交换次数和三次反转不同三次反转每次reverse是两两交换三次反转总交换次数大约n/2 k/2 (n-k)/2 n次环形替换则是n次赋值加n次临时保存。实际执行时间差距很小但环形替换的写法更容易被面试官追问“为什么不会死循环”“环的数量怎么推导”能讲清楚就是明显加分。三种解法放在一起复杂度对比如下解法时间复杂度空间复杂度原地修改实现难度额外数组映射O(n)O(n)否低三次反转O(n)O(1)是中环形替换O(n)O(1)是高3. 实操验证从本地调到LeetCode提交3.1 构造测试用例把边界全打一遍刷题最忌讳“只跑题目的示例”。轮转数组这道题的边界条件相当多我建议本地至少准备这么一组用例用例输入k期望输出考察点普通用例[1,2,3,4,5,6,7]3[5,6,7,1,2,3,4]基本正确性k大于n[1,2,3,4,5,6]8[5,6,1,2,3,4]取模k等于n[1,2,3,4]4[1,2,3,4]取模后为0k等于0[1,2,3,4]0[1,2,3,4]不做任何操作单元素数组[5]5[5]长度1时任何操作都无意义空数组[]3[]注意n0时取模要先判断n与k互质[1,2,3,4,5]2[4,5,1,2,3]环形替换单环覆盖全部n与k不互质[1,2,3,4,5,6]2[5,6,1,2,3,4]环形替换多环尤其注意空数组的情况k % n在n0时会抛出除零异常所以要先判断if (nums null || nums.length 0) return;。LeetCode的测试用例未必覆盖到你但本地验证和面试手写时这就是隐藏扣分点。3.2 本地搭建最小验证环境我用Java演示其实任何语言都一样。把三种解法封装到同一个类里再用main方法跑断言中间可以打印每次反转/替换后的数组方便观察过程是否正确。public class RotateArrayDemo { public static void main(String[] args) { int[] nums1 {1, 2, 3, 4, 5, 6, 7}; rotateByReverse(nums1, 3); System.out.println(Arrays.toString(nums1)); // 期望 [5, 6, 7, 1, 2, 3, 4] int[] nums2 {1, 2, 3, 4, 5, 6}; rotateByCycle(nums2, 2); System.out.println(Arrays.toString(nums2)); // 期望 [5, 6, 1, 2, 3, 4] } public static void rotateByReverse(int[] nums, int k) { int n nums.length; if (n 0) return; k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } public static void rotateByCycle(int[] nums, int k) { int n nums.length; if (n 0) return; k % n; if (k 0) return; int count 0; for (int start 0; count n; start) { int cur start; int prev nums[start]; do { int next (cur k) % n; int temp nums[next]; nums[next] prev; prev temp; cur next; count; } while (cur ! start); } } private static void reverse(int[] nums, int i, int j) { while (i j) { int t nums[i]; nums[i] nums[j]; nums[j] t; i; j--; } } }在本地跑这种demo的好处是可以随手加打印语句观察每一步结果。我第一次调环形替换时就是靠打印发现count没有加在正确位置导致明明环已经走完但仍然死循环。调试器断点固然可以用但对数组下标循环这种场景打印中间态往往更快。3.3 提交时常见的几个失误最典型的失误是Python切片写法没加nums[:] 直接写nums ...。这会导致函数内部创建了一个新的局部列表原数组纹丝不动LeetCode判题直接报错。其次是把返回类型搞错比如Java版本写出public int[] rotate改了签名自然编译不过。第三个失误是三次反转法的区间写错。比如把第二次反转写成reverse(nums, 0, k)多转了一个元素或者第三次反转写成reverse(nums, k 1, n - 1)漏掉一个元素。这些边界在k3、n7的用例下不一定立刻看出来但用k1、n2这种极小用例一跑就原形毕露。我的习惯是写一个通用的reverse方法之后每次都从边界用例先验证。第四个失误发生在环形替换里把do-while误写成while导致第一个起点位置对应的环没有执行替换就直接退出因为cur初始等于start。环形替换必须保证“至少走一步”所以至少用do-while或者在while之前手动执行一次。4. 工程实践轮转思想在真实项目里的应用4.1 环形缓冲区与滚动窗口轮转数组不只是面试题它背后对应着计算机系统里无处不在的“环形”思维。最常见的工程案例就是环形队列底层用固定长度数组维护一个head指针和当前长度出队入队时用(head offset) % capacity定位元素。当你需要把整个缓冲区的内容“回退”或者“前移”若干步时本质上就是做一次轮转操作。比如音视频播放器里的音频环形缓冲区写入端不断把数据追加到写指针位置读取端从读指针消费数据。如果播放器支持seek拖动进度条需要把读指针向后移动这等价于把缓冲区的有效数据段“轮转”到新的起点。虽然实际代码里不会真的物理移动数组元素而是直接移动指针但理解的数学模型和轮转数组完全一致位置加上一个偏移量然后对长度取模。另一个场景是滑动窗口中的“滚动日志”。运维系统里常见的日志滚动log rotation是删除旧文件、创建新文件属于广义的“旋转”。如果把整个日志列表看成数组按时间周期滚动输出同样符合轮转的语义。4.2 从JDK标准库看轮转的工程实现很多语言的标准库已经内置了轮转操作研究它们的实现比死背题解更有价值。Java的java.util.Collections类里有个rotate(List? list, int distance)方法底层实现就是今天说的三次反转思路。JDK源码的逻辑大致是如果list支持RandomAccess比如ArrayList就分别反转两个区间size小的时候还会用更省事的“交换整段”的算法。本质上Collections.rotate就是把[0, n-distance)和[n-distance, n)两段互换位置。Python里没有直接的list.rotate方法但可以用切片nums[:] nums[-k:] nums[:-k]语法上非常优雅代价是O(n)空间。如果要求原地且O(1)空间就回到上面的三次反转。工程上如果代码可读性优先、且数据量不大直接用切片完全没问题但当你处理的是大数组、内嵌在性能敏感路径上时两次反转比切片少分配一个大对象GC压力更小。从这个角度看刷题学到的三种解法并非纸上谈兵标准库作者早就把高频套路写成了官方实现我们手写一遍等于理解了“为什么标准库要这么写”。4.3 位点回退与循环分页在消息队列的消费场景中位点offset回退是一个很实际的操作。消费者组误处理了一批消息想要从更早的位点重新消费本质上就是把当前消费指针向前回退。如果各位点是顺序整数回退就是“下标减去偏移量再对消息总数取模”。一个完整的“从头再来”相当于把消息序列轮转了一圈。循环分页也用到取模下标的惯用法。比如某些业务要求“无限滚动分页”第一页的下一页永远存在每页大小固定页号对总量取模。这种场景的底层计算和(i k) % n如出一辙只是把“数组”换成了“数据库主键列表”。掌握轮转数组等于掌握了这类循环取模下标的基础模型。5. 从这道题延伸出的思考刷题与工程的平衡轮转数组被收录进热题100不只是因为它简单而是因为它能牵出一整片知识网络。三次反转法在“反转单词顺序”“矩阵旋转90度”里会被反复用到环形替换法的gcd推导在“链表环检测”“循环数组相关题目”里也有影子额外数组法虽然空间不是最优但它是“空间换时间”思维的典型例子。把这三条线串起来比背下这一道题的价值大得多。面试的时候我的建议是先给出额外数组映射作为baseline再用“能否优化空间复杂度”这句话引出三次反转。如果面试官深入追问再拿出环形替换并把gcd(n, k)的推导过程讲出来。这种层层递进的节奏体现的不是“背题”而是“理解题目空间”。我自己在实际面试中遇到过几次追问几乎都集中在环形替换的退出条件上。很多人代码能写对但说不清为什么用count说不清环的数量为什么是gcd。建议你在刷完这道题后手动推导n7、k3和n6、k2这两个例子一个环覆盖全部一个分成两个环亲身验证一次比看十遍题解都管用。最后再分享一个小技巧如果你想检验自己是不是真懂了轮转数组可以试着把题目改一下——向左轮转k位、原地翻转整个数组再轮转、在链表中实现同样的轮转。每一个变体都跑一遍你会发现核心不离取模、分段反转和环状替换这三板斧。到那个时候这道题才真正从“做过”变成了“会做”。
