力扣hot100第10题轮转数组这道题在很多人看来属于“数组入门级”的题目但真正刷过一遍之后你会发现它能串起来的考点比你想象的多得多。我面试过不少人也帮不少同学做过面试前的模拟这道题翻车率其实不低。最常见的翻车点有两个一是只会暴力解被追问原地算法时卡壳二是边界条件处理不过关k没做取模就直接反转样例能过但一提交就报错。这篇文章我就把这道题从头到尾拆开来讲四种解法的思路、复杂度、代码、以及面试官可能追问的问题全部捋一遍。1. 题目理解与核心考点拆解1.1 题目到底在说什么先把这个题目本身说清楚。给你一个数组 nums比如 [1,2,3,4,5,6,7]再给你一个非负整数 k你要把整个数组向右轮转 k 个位置。轮转的意思是数组末尾的元素会被“顶”到最前面来类似一个循环队列在往前推进。k1 时 [1,2,3,4,5,6,7] 变成 [7,1,2,3,4,5,6]k3 时变成 [5,6,7,1,2,3,4]。题目本身非常简短但里面藏着一句关键的话k 是非负整数。这代表 k 可以大于数组长度甚至可能是一个非常大的数这一点在后面的实现里必须处理。不做 k % n 的去重处理很多解法都会出错尤其是在用三次反转法时第二次反转的区间长度一旦超过数组长度就必然越界。1.2 这道题考的是什么这道题的官方难度是中等但实际面试中它的定位很微妙。它不像二叉树的遍历那样需要你背一堆模板也不需要复杂的动态规划状态定义它考察的是最基础也最容易被忽视的能力对数组下标的掌控力、对时间空间复杂度的权衡意识、以及在写代码时对边界条件的敏感度。在hot100里它排在第10位属于高频题中的高频题。我自己的判断是这道题是检验一个人“基本功是否扎实”的试金石。能写出暴力解说明你知道题目在问什么能写出额外数组解说明你具备基本的空间换时间思维能写出三次反转说明你理解数组操作的深层规律而能稳定写出环状替换并说出每一步的原因说明你确实吃透了原地算法。四个层次基本可以把候选人的水平拉开。2. 解法一与解法二暴力法和额外数组法2.1 暴力模拟思路最直白但最容易超时先讲最容易想到的暴力法。既然要右移k次那我每次把数组右移一位循环k次。右移一位的具体操作是先记住最后一个元素然后把前面所有元素依次往后挪一格最后把记住的最后一个元素放到开头。写成代码大概是这样def rotate(nums, k): n len(nums) k % n for _ in range(k): last nums[-1] for i in range(n - 1, 0, -1): nums[i] nums[i - 1] nums[0] last思路没有错但它的时间复杂度是 O(n*k)。就算你记得对 k 取模当数组长度是 10^5、k 也是 10^5 级别时操作次数依然能达到 10^10 量级大概率直接超时。这也是力扣上样例可能让你通过但提交后跑大数据用例就挂掉的典型场景。我特别想强调一点暴力法虽然效率低但它不是没有价值的。它是理解后续所有优化方案的基准线面试官往往会从暴力解开始引导你问你“这个解法哪里不好能不能优化”所以你得能准确说出它的性能瓶颈在哪。你能指出“每次右移一位都要移动整个数组导致总操作次数是 n 和 k 的乘积”这句话一出来后面的优化方向就顺理成章了。2.2 额外数组法用空间换时间的典型暴力法太慢那很自然的想法是我能不能一次就把每个元素放到它最终应该在的位置当然可以。核心是一个很简单的映射关系原数组中下标为 i 的元素向右轮转 k 位之后它的新下标是 (i k) % n其中 n 是数组长度。基于这个公式开一个新的等长数组把每个元素放到位最后再复制回原数组def rotate(nums, k): n len(nums) new_arr [0] * n for i in range(n): new_arr[(i k) % n] nums[i] for i in range(n): nums[i] new_arr[i]时间复杂度 O(n)空间复杂度 O(n)。这个解法的优点是极其直观几分钟就能写对而且几乎不可能出错。缺点是用了额外数组空间复杂度不符合题目的进阶要求。面试中当你先给出暴力解、被提示“能不能一次放到位”时额外数组法就是最顺理成章的下一步。但它不是终点因为面试官大概率会追问那句经典的话“能不能用 O(1) 的额外空间完成”这时候你就需要转移到原地算法。顺便提一句Python 里复制回原数组可以用nums[:] new_arr省掉一个循环简洁不少面试时能少写几行是一行。提示额外数组法虽然空间复杂度高但它给出了轮转问题的核心映射公式。后面所有原地解法的正确性最终都能用这个公式来验证。所以在刷题时不要只把它当过渡方案它也是你做测试时判断结果对不对的“标尺”。3. 解法三环状替换原地算法真正的思维考验3.1 环状替换的核心思想现在进入这道题真正有思维含量的部分。前面额外数组法的映射公式给了我们一个灵感既然每个元素都能算出它要去的新位置那我能不能不借助额外数组直接在原数组上“滚动”完成想象这个过程从某个起点位置 curr 开始把它的元素拿出来放到它该去的位置 next。被覆盖位置的元素又成了新的“手上元素”继续放到它该去的位置。这样一路往后会沿着一条环形的链路前进这就是环状替换也叫循环替换。举个具体例子。nums [1,2,3,4,5,6]k 2。从下标0开始nums[0]1 应该去 (02)%62所以把1放到下标2手上拿着被覆盖的 nums[2]3。下标2应该去 (22)%64把3放到下标4手上拿着 nums[4]5。下标4应该去 (42)%60把5放到下标0回到起点这一圈完成。走完这一圈我们发现只移动了3个元素。但数组一共6个元素剩下的3个还没处理。这正是环状替换最容易被卡住的地方从下标0出发的链不一定能覆盖到所有下标。3.2 实现细节与几个关键判断为什么一条链走不完所有元素因为当 n 和 k 的最大公约数大于1的时候gcd(n, k) 决定了环的个数每个环的长度是 n / gcd(n, k)。比如 n6、k2gcd2就有两个环一个包含下标 0,2,4另一个包含下标 1,3,5。代码实现上处理这个问题的通用方案是用一个 count 变量记录已经移动过的元素个数。每移动一个元素 count 加1当 count 等于 n 时整个数组就都在正确位置上了。至于什么时候换起点最稳妥的策略是从0开始递增每次完成一个环后如果 count 还小于 n就换下一个起点进入新的环。def rotate(nums, k): n len(nums) k % n if k 0: return count 0 start 0 while count n: curr start prev nums[start] while True: nxt (curr k) % n nums[nxt], prev prev, nums[nxt] curr nxt count 1 if curr start: break start 1这里有个特别容易踩的坑如果你在进入循环前单独多移动了一次或者在环内移动了 n/gcd 次之后还没判断回到起点会导致下标处理混乱。我用 count 计数法最保险因为逻辑上只有两个出口环回到了起点或者整个数组已经全部处理完。这两个条件都判断清楚代码就不会乱。3.3 有没有更简单的写法老实说环状替换在面试里不是必须的。我见过不少准备得很充分的候选人能写出三次反转但让他写环状替换还是会卡壳这很正常。环状替换的价值更多在于展示你对“下标映射”和“循环链”的理解。有的面试官本身就在考察这一类思维而不是单纯追求一个答案所以有余力的话最好还是把它搞懂。如果你实在不想在环状替换的边界判断上花太多时间我教你一个记忆技巧整段代码的核心其实就是“跟着元素走”从起点出发用下一个位置覆盖当前位置一直走到回到起点。配合一个 count 保证不会有一个元素被漏掉。不要先在草稿纸上推导出所有下标再写代码直接让代码跟着指针走反而更容易一次写对。4. 解法四三次反转面试中最推荐的正解4.1 三次反转为什么能成立说完了环状替换我来说这道题在实际面试里我最推荐的解法三次反转。它代码量最少、最好理解而且是原地操作空间复杂度 O(1)时间复杂度 O(n)完美符合题目进阶要求。三次反转的思路非常巧妙。先看一个现象把一个数组分成前后两段前段是前 n-k 个元素后段是后 k 个元素轮转之后后段整体挪到了前面前段整体挪到了后面。这本质上就是“把两段元素的顺序交换”。而“交换两段”这件事可以通过三次反转完成先反转整个数组让两段内部的顺序各自颠倒但两段的相对位置发生调换。再反转前 k 个元素把第一段内部的顺序恢复。再反转剩下 n-k 个元素把第二段内部的顺序恢复。用数学语言来说反转操作有“逆序抵消”的性质。不用被术语吓到直接看例子就明白。4.2 代码实现与注意事项以 nums [1,2,3,4,5,6,7]k 3 为例整体反转[7,6,5,4,3,2,1]反转前 3 个元素[5,6,7,4,3,2,1]反转后 4 个元素[5,6,7,1,2,3,4]三次反转正好得到题目要求的结果。代码长这样def rotate(nums, k): n len(nums) k % n reverse(nums, 0, n - 1) reverse(nums, 0, k - 1) reverse(nums, k, n - 1) def reverse(nums, left, right): while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1我强烈建议你把 reverse 这个子函数单独摘出来。面试中大概率还会遇到其他需要反转的变体题比如反转字符串、反转链表都会用到差不多的双指针思路。把这个小函数写好等于给自己备好了高频件。这里有一个非常重要的细节第二次反转前 k 个元素这个 k 必须先做过取模运算。如果忘了 k % n比如数组长度是 7、k 是 10那第二次反转前 10 个元素就会直接数组越界。还有另一种更隐蔽的错法是把第二次反转写成了前 n-k 个也会导致结果完全不对。4.3 k的处理一个轻易踩中的大坑我把 k 的处理单独拿出来讲因为这是这道题最容易翻车的地方。题目说 k 是非负整数但它可能比 n 大。轮转的本质是循环轮转 n 次等于数组回到原样所以 k 的有效值其实就是 k % n。举个例子n7k10向右轮转 10 次等价于轮转 3 次因为转满 7 次就复位了。所以不管用哪种解法第一步都应该先做 k % n。如果用的解法是在循环里模拟 k 次这一步能省掉大量无效操作如果用的是下标映射或反转这一步能防止数组越界。我见过不少同学暴力法里没做取模k 很大时直接超时反转法里没做取模第二次反转直接跑出界。这个步骤真的要养成肌肉记忆。还有一个小问题如果 k % n 0比如 k 正好等于 n或者 k 0这时数组不需要任何调整。好在三次反转的代码天然兼容这个情况因为反转长度为 0 的区间不会报错函数直接返回。但如果你手写其他解法可以先做一个早期返回省掉不必要的操作。5. 常见问题与排查思路实录5.1 高频Bug清单这道题虽然代码不长但实际写的时候大家遇到的坑还真不少。我整理了这几类高频Bug你可以对照排查。第一类忘记取模。症状是提交时有的用例通过、有的越界或者结果完全不对。很多面试者的第一反应是“刚才不是还好的吗”其实换一个 k 大于 n 的用例就暴露了。建议在代码第一行就写 k % n形成条件反射。第二类反转区间边界写错。三次反转最常见的边界错误是第二次反转写成 reverse(nums, 0, k) 而不是 reverse(nums, 0, k-1)或者把第三次反转写成了 reverse(nums, k1, n-1)。写的时候要把区间是左闭右闭这个约定在心里反复确认。我用的是左闭右闭区间你也可以用左闭右开区间但一定要统一不要混用。第三类环状替换时 count 和返回条件处理乱。典型错误是内层 while 把 start 更新为 nxt导致外层永远找不对下一个起点。我的建议是内层环的起点用一个单独的变量 start 记录内部指针用 curr两个变量别混用。还有环内的循环退出条件建议用 curr start而外层的退出条件用 count n这两个判断的逻辑要完全分开。第四类空数组和长度为1的数组。题目一般不包含空数组但长度为1的数组在 k 任意值下都应该原样返回。取模后 k 一定为0代码自然没问题但如果你在 if k0: return 之前就访问了 nums[-1] 这类操作就要小心越界。5.2 测试用例设计思路面试时写完了代码不要急着说“我写完了”你得主动给出几个测试用例来验证。这不仅显得专业也能在关键时刻救自己一命。我常用的测试用例集是这样设计的用例类型输入预期输出设计目的功能正常用例[1,2,3,4,5,6,7], k3[5,6,7,1,2,3,4]验证主流程正确k大于n[1,2], k3[2,1]验证是否做取模k等于n[1,2,3], k3[1,2,3]验证轮转一周复位数组长度为1[5], k100[5]验证极端情况不互质用例[1,2,3,4], k2[3,4,1,2]暴露环状替换的环数问题最后一个用例对环状替换尤其重要。n4、k2 时最大公约数是2数组会分成两个环。如果你环状替换的起点切换逻辑写错了这个用例最容易暴露问题。我在给别人做代码评审时几乎每个环状替换写得有问题的版本都会被这个用例打回来。5.3 面试追问与应对我把面试官可能追问的几个问题也整理出来提前想好怎么回答现场就不会慌张。追问一“如果 k 是负数怎么办”这道题规定 k 非负但如果面试官问变体你要意识到向右轮转 -k 位等价于向左轮转 k 位也等价于向右轮转 n-k 位。所以在三次反转法里把 k 修正为 ((k % n) n) % n就能处理所有整数 k。追问二“能不能原地解决”这个直接展示三次反转或环状替换就行。你最好能指出额外数组法的空间复杂度是 O(n)而你的解法是 O(1)两句话把权衡说清楚显得你对复杂度有清晰的意识。追问三“如果数组非常大一次装不进内存怎么办”这属于分布式场景题通常思路是分块处理或借助外部存储比如把数组分块后按块轮转但块内顺序还要保持是个比较开放的讨论题。能接上这个话题说明你不只是一个刷题机器还有工程思维。追问四“轮转操作在工程里一般用在哪些场景”这就需要一个日常业务的积累。比如模拟滚动日志文件里的滑动窗口音频数据的循环播放时做偏移还有游戏里地图循环滚动的坐标映射。不用说得太深能举出两三个实际例子就行。6. 相关题目与实际应用场景6.1 和这道题高度相关的力扣题目刷题最重要的能力之一是把题目串成网络。轮转数组相关的变体题有好几个建议你连着刷会有一种举一反三的畅快感。第一道是“反转字符串中的单词”比如输入 the sky is blue要输出 blue is sky the。思路是先把整个字符串反转再把每个单词反转回来。这和三次反转的思路几乎一致区别只是第三次反转的区间需要根据空格动态切分。第二道是“旋转链表”给定一个链表的头节点把链表向右旋转 k 个位置。链表版的核心是先求出长度取模再找到新头节点的前驱切断并重连。虽然数据结构不同但你处理 k 的方式和这道题完全一样。第三道是“反转字符串 II”考察的是按区间反转本质还是双指针 reverse 函数的灵活运用。第四道是“寻找旋转排序数组中的最小值”或者“搜索旋转排序数组”它虽然把“轮转”变成了“旋转”但这个旋转操作本身正是这道题在做的事情。理解轮转数组的最终形态再看那些二分搜索解法会轻松很多。6.2 轮转思想在真实业务里的影子如果你觉得自己刷题和工程脱节那轮转数组恰好是那种能让你在面试里说出“这个我在实际中见过”的题。举几个我遇到过的场景。第一个循环队列 buffer。在嵌入式或者网络库的代码里环形缓冲区经常要做“读指针偏移”这本质就是一次数组轮转的局部版本关键点在于下标取模。第二个数据平滑窗口。比如股票K线图的最近 N 天数据每来一条新数据整个窗口要“左移抛弃最旧、右端加入最新”很多实现看起来操作的是队列但如果底层是数组核心下标更新就是轮转那套逻辑。第三个图像或音频水印的位移处理。某些加密算法或者数字水印方案里需要对像素矩阵做基于行的循环位移这和轮转数组是同一种数学操作。我在参与过的一个图像处理Demo项目里就做过类似功能那时用的辅助数组后面重新优化成原地反转法性能提升很明显内存占用也降下来了。这些场景不一定要在面试里主动大谈特谈但如果面试官问“这题有什么实际价值”你有真实案例可讲会是很加分的。最后说一点个人体会。轮转数组看似简单但它的四种解法恰好覆盖了从初级到进阶的完整能力链条。我最开始刷这道题时也只会暴力法后来看到三次反转的解法觉得太神奇了但并没有真正理解为什么能成立。直到系统复习了反转操作的性质再亲手推导了一遍下标变化才算彻底想透。所以我的建议是这道题不要只背代码亲手推导一遍下标变化把四种解法都写一遍再试着口头讲解给别人听你会发现它带给你的提升不止是一道题的AC而是对整个数组操作体系的理解。面试前的最后一天再来看这道题我保证你还会有新的收获。