这道LeetCode 189题“轮转数组”表面上是把数组元素往后挪几个位置实际上它是数组类题目里非常典型的“一题多解”样本。面试官喜欢拿它来考察你对原地修改、边界条件、数学推导的掌握程度而不只是看你会不会调API。适合准备算法面试的人、刚学数据结构的学生以及平时工作中要处理大量数据搬移场景的工程师。我第一次做这题的时候下意识就是开一个新数组用(i k) % n计算出每个元素的新位置三分钟写完了。但马上意识到这是空间复杂度 O(n) 的解法数据量一大就不好看。真正让这题值钱的地方是它能在 O(1) 空间内完成轮转也就是“原地旋转”的功夫。今天这篇文章就把我在这道题上踩过的坑、总结出的解法思路完整写下来。1. 问题定义与思路拆解1.1 题目要求和最容易忽略的边界条件轮转数组的题目描述并不复杂给定一个整数数组 nums将数组中的元素向右轮转 k 个位置。举个例子nums [1,2,3,4,5,6,7]k 3轮转后是[5,6,7,1,2,3,4]。注意“轮转”和“移动”的区别轮转是循环的末尾被挤掉的元素会从头部绕回来而不是丢弃。看到题目后我建议你先停下来想一下有哪些边界条件。大部分人栽跟头就栽在这些地方。当k 0或者k nn是数组长度时数组不变很多实现会在这里出错。当k比n大时比如n 5, k 12实际有效轮转次数是k % n 2不取模就会越界或者多做无用功。当数组为空或只有一个元素时任何轮转都不改变数组需要提前处理。有些版本还会问k为负数也就是向左轮转这种情况可以转换成n - abs(k)处理。这些边界条件不是刁难它们反映了一个程序员的防御性编程习惯。我自己的习惯是拿到题先写测试用例空数组、单元素数组、k 0、k n、k n把这几个用例跑通了代码基本就稳了。1.2 从暴力解法到空间换时间再到原地操作轮转数组的解法我把它分成三个层次这也是我建议初学者依次去尝试的路径。第一层是暴力移动每个循环向右挪一位重复k次。这个解法的时间复杂度是 O(n * k)空间是 O(1)。思路最简单但k一大就完全不可用比如n 100000, k 99999基本上就是灾难现场。暴力解法的意义在于帮助理解“轮转”的本质过程但不应该作为最终答案。第二层是使用辅助数组把nums复制一份然后遍历原数组把nums[i]放到temp[(i k) % n]里。这个解法的代码很简洁时间 O(n)空间 O(n)。因为用了额外数组逻辑上几乎不存在出错的可能。这也是我上面说的“三分钟写完”的方案。它的问题在于空间上多了一倍的消耗在数据量极大的场景下不够优雅。第三层才是面试官真正想看的原地操作也就是空间 O(1) 的解法。实现原地轮转有两条路线一条是三次反转法另一条是循环替换法。这两条路线各有特点接下来详细拆解。2. 三次反转法的原理推导与多语言落地2.1 为什么“反转再反转”就能完成轮转三次反转法的核心思想我尽量用人话讲清楚。假设数组是[1,2,3,4,5,6,7]k 3期望结果是[5,6,7,1,2,3,4]。如果我们把数组看成两段前面n-k个元素是 A 段[1,2,3,4]后面k个元素是 B 段[5,6,7]。轮转的本质就是把 B 段整体挪到开头A 段整体挪到结尾同时两段内部元素的相对顺序不变。为什么三次反转能实现这个效果我们一步步走第一次反转把整个数组反转。[1,2,3,4,5,6,7]变成[7,6,5,4,3,2,1]。此时原来的 B 段倒序出现在前面原来的 A 段倒序出现在后面。第二次反转把前k个元素反转。前k个元素是[7,6,5]反转成[5,6,7]。B 段内部恢复原序并且已经排在了数组的最前面。第三次反转把后n-k个元素反转。后n-k个是[4,3,2,1]反转成[1,2,3,4]。A 段内部恢复原序并且排在数组的后面。最终得到[5,6,7,1,2,3,4]。这里面的关键点是“反转抵消”。一次反转会把一片区间的元素顺序颠倒两次操作如果作用在同一区间就能恢复原序如果作用在不同区间就是在整体颠倒的基础上分别恢复各区间的内部顺序。轮转操作的本质就是“把数组切两段交换这两段的位置”而“整体反转再局部反转”恰好是一种不需要额外空间就能交换两段的方法。注意k必须先做取模运算k % n确保k n。如果不做这一步第二次反转的区间边界就可能越界这是最典型的低级错误。2.2 C 与 JavaScript 的实现细节先看 C 的实现C 标准库自带std::reverse可以很方便地反转指定区间#include vector #include algorithm using namespace std; class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); if (n 0) return; k % n; if (k 0) return; reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() k); reverse(nums.begin() k, nums.end()); } };注意这里的k 0判断是从k % n之后开始的如果 k 是 n 的整数倍那就不需要做任何操作提前返回可以省掉三次无意义的反转。JavaScript 版本的坑在于数组没有内置“反转指定区间”的方法所以自己写一个双指针交换的辅助函数function rotate(nums, k) { const n nums.length; if (n 0) return; k % n; if (k 0) return; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } function reverse(nums, left, right) { while (left right) { [nums[left], nums[right]] [nums[right], nums[left]]; left; right--; } }这里用了解构赋值交换元素代码很简洁但要注意如果k 0第二次反转传入的right -1while 循环不会进入不会有问题。JS 里另一个常见坑是有人习惯用nums.slice()但slice返回一个新数组不会修改原数组这一点在数组方法的使用上要注意。TypeScript 版本和 JavaScript 几乎相同只是加上类型标注这里不重复贴代码。重点是理解反转的思想而不是死记某一门语言的 API。3. 原地轮转的另一条路循环替换法与环数计算3.1 用“座位交换”类比循环替换法三次反转法虽然代码短但从“为什么有效”的角度理解起来有一个跳跃。循环替换法则是从另一个角度出发的它模拟了“每个人按规则换到新座位”的过程。想象一下一个教室里有 n 个座位座位编号 0 到 n-1。现在要求每个人从座位 i 换到座位(i k) % n去。如果我们从 0 号座位开始先让 0 号座位上的人坐到k号位那k号位原来的人就被挤出来了接着让这个被挤出来的人去坐(k k) % n号位又被挤出来的人继续往下走。这个过程一直持续到回到起点 0 号位此时一个“置换环”就处理完了。举一个具体的例子nums [1,2,3,4,5,6]k 2。从 0 号位开始nums[0] 1目标位置是 2把 1 放到 2 号位此时nums[2]原值 3 被挤出来。带 3 去 4 号位nums[4]原值 5 被挤出来。带 5 去 0 号位因为(4 2) % 6 0把 5 放到 0 号位回到起点。一个环结束处理了 0、2、4 三个位置。但此时 1、3、5 三个位置还没有处理。所以需要从 1 号位再开始一个环1 - 3 - 5 - 1。两个环都处理完整个数组就轮转完成。这个例子里我们经历了两个环。那环的数量是怎么确定的为什么有时是一个环有时是两个环3.2 环的数量为什么是 n 和 k 的最大公约数如果把索引变化看成一个映射f(i) (i k) % n从任意一个起点出发不断应用映射最终会回到起点形成一个环。环的长度 L 是最小的正整数使得L * k是 n 的倍数也就是i L*k在模 n 的意义下等于i。这个最小的 L 等于n / gcd(n, k)其中 gcd 是最大公约数。因为每个环的长度都一样所以环的数量就是n / L gcd(n, k)。举个例子n 6, k 2gcd(6,2) 2所以有 2 个环每个环长度是 3和我们上面推演的一致。再比如n 7, k 3gcd(7,3) 1所以只有 1 个环环长 7指针最终会遍历所有位置。所以循环替换法的整体结构是外层循环从 0 到 gcd-1分别以每个位置作为起点内层循环沿着环一直走直到回到起点。代码实现如下#include vector using namespace std; class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); if (n 0) return; k % n; if (k 0) return; int cycles gcd(n, k); // 环的数量 for (int start 0; start cycles; start) { int cur start; int prev nums[start]; do { int nxt (cur k) % n; int temp nums[nxt]; nums[nxt] prev; prev temp; cur nxt; } while (cur ! start); } } int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } };这里有个容易写错的地方do...while至少会执行一次因为从一个起点出发第一次移动一定不是回到起点只要 k 不为 0 且 n 大于 1。如果用while (cur ! start)作为循环条件就需要在进循环前先手动走一步很容易弄乱。使用do...while直接保证先移动再判断逻辑更清晰。3.3 两种原地算法怎么选三次反转法和循环替换法都能达到 O(1) 空间、O(n) 时间但实际使用体验差别不小。我整理了一张对比表对比维度三次反转法循环替换法代码量极短核心就三行反转较长需要写 gcd 和环遍历理解成本较低但原理需要体会较高需要数论基础元素赋值次数每个元素被反转两次约 2n 次每个元素被移动一次约 n 次出错概率低边界好控制较高环的起点和循环条件容易错面试表现推荐清晰易懂加分项展现数学功底从面试的角度我一般推荐先写三次反转法因为它代码短、不易出错而且大部分面试官都能立刻看懂。循环替换法更适合作为“进阶解法”在面试中主动补充或者在实际高性能场景下使用因为它的元素搬移次数更少在数组特别大时少一些 cache 失效的损耗。4. 工程场景里的轮转数组与避坑清单4.1 真实业务中的轮转需求有人觉得轮转数组只是面试题实际工作中用不到这个观点我不太同意。轮转的本质是循环队列的索引偏移业务场景很常见。我举几个自己见过的例子。播放器的循环播放列表当前播放的是第 i 首歌用户点击下一曲之后指针变成(i 1) % n本质就是一次步长为 1 的轮转。轮播图的自动播放、广告位的定时切换底层都是同一个逻辑。消息队列中消费者从环形缓冲区读取数据缓冲区满时覆盖最旧的数据这也是一个“数组轮转”的变体。还有图像处理中的像素矩阵旋转、游戏里地图块的滚动拼接都和数组的位移操作相关。在这些场景里如果数据量大到上百万用 O(n) 的辅助数组复制来复制去内存占用会很难看。理解了原地轮转的原理在写业务代码时就会下意识去考虑“这个操作能不能原地完成”这个意识本身就是成长。4.2 不用手写算法的“轮子”数组方法与标准库工程开发中其实没有必要每次都手写反转算法主流语言基本都有现成的实现。我在这里把常见方案列一下。C 的标准库提供了std::rotate注意它是左旋函数右旋 k 位等价于左旋n - k位#include algorithm #include vector using namespace std; void rotateRight(vectorint nums, int k) { int n nums.size(); if (n 0) return; k % n; rotate(nums.begin(), nums.begin() n - k, nums.end()); }Python 可以用切片拼接非常简洁def rotate(nums, k): n len(nums) k % n nums[:] nums[n - k:] nums[:n - k]注意是nums[:] ...而不是nums ...前者修改原列表后者只是重新绑定一个新对象外部引用感知不到变化。这个细节很多人踩过坑。JavaScript 没有原生的指定区间反转方法但可以用splice和unshift组合function rotate(nums, k) { const n nums.length; if (n 0) return; k % n; const removed nums.splice(n - k, k); nums.unshift(...removed); }不过unshift(...removed)在k很大时会有参数展开的栈溢出风险更保险的方式是用slice加splice覆盖function rotate(nums, k) { const n nums.length; if (n 0) return; k % n; const tail nums.slice(n - k); // 先把前 n-k 个元素整体后移再把 tail 放到开头 for (let i n - 1; i k; i--) { nums[i] nums[i - k]; } for (let i 0; i k; i) { nums[i] tail[i]; } }这些工程方案本质上都借助了语言的数组方法能力比如 JS 里的splice、slice、unshiftPython 的切片C 的标准库算法。但注意很多数组方法内部依然有 O(n) 的拷贝操作如果你处理的是几千万级别的数据且对内存敏感还是值得回到手写的原地算法。4.3 高频问题与排查技巧这一节我把自己实际调试中遇到的典型问题整理成一个速查表写题或者写业务代码时可以直接对照排查。现象原因解决方案数组越界异常k没有取模反转区间超出边界在入口处k % n结果和预期完全错位反转顺序不对或者反转区间搞反先在纸上画小数组标记三段边界轮转后元素丢失使用了切片但没把结果写回原数组Python 用nums[:]JS 用 splice 修改原数组循环替换时死循环外层循环从 0 到 n-1导致重复处理同一个环外层循环次数应该是 gcd(n, k)而不是 nk 0时出现意外修改没有提前判断取模后的 k 是否为 0k % n后增加if (k 0) return;单个元素的数组报错反转前检查长度否则 n-1 为负数入口处if (n 2) return;排查这类问题我有一个从实际调试中总结出来的方法用[1,2,3,4,5,6]这种相邻整数组成的数组手动推演一遍三个反转区间再把每一步打印出来看。只要中间某一步的数组和手算的预期对不上问题就定位了。尤其是三次反转法步骤少非常适合断点调试。热词里有一个“C#中如何判断一维数组是否为空”这其实也是边界处理的问题。C# 里数组为空通常指arr.Length 0但更稳的做法是同时判断arr null。算法题里我们默认入参合法但工程代码里这种边界判断一定要做。轮转数组这道题教会我的不是反转函数怎么写而是“任何一步操作之前先确认边界条件是否安全”这个习惯比背下所有算法都值钱。写在最后的一点体会轮转数组这道题我的建议是不要死背代码而是把“取模处理边界、整体反转补偿局部反转、循环替换时先数环”这几个思维动作变成直觉。我第一次在面试现场写这题因为忘了对 k 取模反转区间直接越界当场被面试官指了出来。后来我给自己定了一个固定套路拿到数组题先写长度和边界判断再写核心逻辑。这个习惯帮我避开了很多不必要的失误。如果你想把数组知识体系再往深走一层可以顺着轮转数组延伸去刷“寻找两个正序数组的中位数”、“约瑟夫环”、“连续子数组乘积最大值”这些题目它们都建立在数组索引和区间操作的基础上。轮转数组只是一扇门打开之后你会发现数组这个“普通”的数据结构其实一点都不普通。