轮转数组算法详解：从临时数组法到原地优化的完整思路

秋招那会儿我刷到“轮转数组”这道题第一反应是这有什么好考的不就是把数组往右挪几步吗真到白板上一写才发现里面全是细节——往哪边转、转几步、要不要原地改、k 比数组长度大怎么办。后来我用最朴素的“临时数组法”把这道题吃透了又顺带对比了反转法、环状替换才算彻底搞明白这类题的套路。这篇东西不是照搬题解是我自己从“能跑”到“跑得明白”的全过程。核心围绕临时数组法展开但也会把其它解法的优劣讲清楚毕竟面试官大概率会追问一句“还能不能优化”。如果你正准备算法面试或者刚开始刷题这篇文章应该能帮你省不少时间。1. 先搞清楚“轮转”到底在考什么语义、方向与取模运算1.1 轮转的语义右移 k 步到底发生了什么轮转数组也叫旋转数组最常见的描述是给定一个数组将数组中的元素向右轮转 k 个位置。注意是“轮转”不是“平移”平移是元素整体挪过去之后空出来的位置用 0 或别的值填充轮转是把尾巴上被挤出去的元素绕到数组头部来形成环形效果。举个例子输入nums [1, 2, 3, 4, 5, 6, 7], k 3 输出[5, 6, 7, 1, 2, 3, 4]从结果上看最后三个元素 5、6、7 被挪到了开头原来的 1、2、3、4 依次后移。这个例子几乎出现在所有题解里但真正动手写的时候很多人会纠结一个问题到底是把“最后 k 个元素挪到前面”还是把“每个元素向右移动 k 个下标”这两句话等价但思考路径完全不同。临时数组法用的是后者对每个位置 i它旋转后的新下标是(i k) % n。理解了这个公式代码就能写对一半。1.2 方向、负数 k 与“k 大于长度”的三重陷阱轮转方向通常默认是右轮转。如果题目说“向左轮转”那映射公式就变成(i - k n) % n。有些变体题会直接给负数 k 表示反向轮转这时需要先统一方向右轮转 k 步等价于左轮转n - k % n步。k 为负数时先右转其实最简单的方法是统一成右轮转k (k % n n) % n。k 大于数组长度是最容易踩的坑。比如nums [1, 2, 3], k 5如果直接拿i 5去算下标会越界。正确做法是k k % 3 2因为轮转 3 次等于没转轮转 5 次等于轮转 2 次。取模运算在这里的语义可以想象成一个环形时钟下标只是在 0 到 n-1 的圈里打转。理解了“环形”这个概念后面所有解法的推导都会顺畅。1.3 从映射公式到可视化为什么(i k) % n是唯一的建议第一次接触这道题时拿出纸笔画一张图。坐标轴写原下标 0 到 n-1再写一行新下标然后一个萝卜一个坑地填原数组 1 2 3 4 5 6 7 下标 0 1 2 3 4 5 6 k3 时 下标 0 的新位置 (03)%7 3 下标 1 的新位置 (13)%7 4 ... 下标 4 的新位置 (43)%7 0你会发现原下标 4、5、6 的新位置分别是 0、1、2正好对应最后三个元素跳到前面。这就在视觉上验证了公式。很多面试者背下了(ik)%n但被问“为什么是这个”时卡住。其实答案很朴素因为数组下标是连续整数轮转就是给每个下标加上一个偏移量再加上模 n 把它拉回合法区间。到这里临时数组法的数学基础就建好了我们不需要移动元素只需要计算每个元素的“新家地址”然后搬到新家。2. 临时数组法的完整推导为什么第一反应是开一个新数组2.1 最直观的算法每个元素直接放到新位置临时数组法简单说就是创建一个和原数组等长的辅助数组遍历原数组把每个元素放到辅助数组的正确位置上最后再把辅助数组的内容拷贝回原数组。它的正确性几乎不需要证明每个元素都去了它该去的地方没有一个元素被覆盖丢失也没有一个位置被重复填入。伪代码大概长这样n nums.length k k % n temp new int[n] for i 0 to n-1: newIndex (i k) % n temp[newIndex] nums[i] for i 0 to n-1: nums[i] temp[i]第一遍写的时候很多人会问为什么不是temp[i] nums[(i - k n) % n]这两个写法其实等效只是视角不同。前者是“从原位置出发找新位置”后者是“从新位置出发找原位置”。我习惯用前者因为遍历原数组时脑子不容易乱。2.2 一个关键问题需不需要处理 k 的符号和大小临时数组法的第一步必须是k % nums.length。如果 k 恰好等于数组长度取模后 k0遍历一遍拷贝回来数组原样白跑一趟。如果不取模i k可能超过 n取模之后虽然结果也对但中间可能出现溢出吗在 Java/C 里如果 k 是 int 且很大比如超过 2^31可能溢出。所以先取模是必要的不是可有可无的优化。负数 k 的处理建议统一成k ((k % n) n) % n;这一行的意思先取模到-n1到n-1的区间再加 n 后取模保证非负。面试时最好主动提一句“如果 k 可能为负我会这么处理”会显得考虑问题周全。2.3 复杂度分析时间 O(n)空间 O(n)临时数组法的时空复杂度非常清晰时间复杂度遍历数组两次一次写临时数组一次拷贝回来所以是 O(n)。空间复杂度额外开了一个等长数组所以是 O(n)。在很多算法教程里O(n) 空间被看作“不够好”因为这道题常见的进阶要求是“原地修改数组空间复杂度 O(1)”。但我不觉得临时数组法是垃圾它有一大堆优点逻辑简单、不容易写错、可以轻松处理各种边界情况而且在实际工程中如果数组不大多一份内存占用完全无所谓。面试时候如果时间紧张先用临时数组法跑通再提优化这是最稳的策略。反过来如果一上来就憋反转法憋半天写错了反而丢分。2.4 空间换时间的取舍不是所有场景都需要“原地”我见过不少刷题新手被“原地”两个字吓到觉得不 O(1) 空间就是错的。其实不然。真实业务里数组轮转通常发生在内存里的小型数组上比如图片像素的平移、列表的循环滚动这些场景下临时数组的额外内存开销微乎其微但代码的可读性大幅提升。我自己的判断标准是如果数组大小在几万以内临时数组法完全可以接受如果数组很大比如千万级或者内存极其紧张才需要考虑原地方案。刷题的进阶要求是练习思路不是每个题都必须用最省空间的解。所以别因为临时数组法空间复杂度高就觉得它“低级”。能把最简单的解法写得干净、正确、可扩展也是一种能力。3. 多语言实现与细节差异从 C 到 Python 的写法习惯3.1 C 实现vector 操作与拷贝陷阱C 中我一般这样写void rotate(vectorint nums, int k) { int n nums.size(); if (n 0) return; k ((k % n) n) % n; vectorint temp(n); for (int i 0; i n; i) { temp[(i k) % n] nums[i]; } nums temp; }这里有几个 C 细节nums.size()返回的是size_t无符号类型如果直接用(-k) % n这类表达式要小心符号转换。所以我习惯先把 k 专门处理成非负值。nums temp是深拷贝会重新分配内存。如果不想重新分配可以用nums.assign(temp.begin(), temp.end())。但刷题时直接赋值最简单。if (n 0)一定要判断否则vectorint temp(n)虽然合法但后面循环不执行不会崩溃不过如果 n0 时 k 取模会除零所以必须先判断。3.2 Java 实现System.arraycopy 与手动循环Java 版本我写过两种。第一种是纯手动循环public void rotate(int[] nums, int k) { int n nums.length; if (n 0) return; k ((k % n) n) % 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); }第二种是用System.arraycopy代替第二段循环。这个 API 是 JVM 底层实现的效率比手写循环略高但刷题时几乎感受不到差距。需要注意的是arraycopy的五个参数源数组、源起始、目标数组、目标起始、长度。写错很容易运行时抛异常。顺便提一个 Java 特有的坑int 溢出。如果 k 是Integer.MAX_VALUE直接i k会变成负数取模后下标就错了。所以先k % n非常必要。这一点在 C 里同样存在但 C 的 signed overflow 是未定义行为更危险。3.3 Python 实现列表推导与切片的优雅与陷阱Python 写起来最像伪代码def rotate(nums, k): n len(nums) if n 0: return k ((k % n) n) % n temp [0] * n for i in range(n): temp[(i k) % n] nums[i] nums[:] temp注意最后一行我用的是nums[:] temp而不是nums temp。前者会原地修改列表后者会让nums指向一个新列表函数外部的引用不会变化。这是 Python 新手最容易踩的坑。如果你只是想实现功能Python 还有更简洁的切片旋转nums[:] nums[-k:] nums[:-k] if k else nums但切片法本质也是创建了新列表只不过把细节藏起来了。面试时如果你这么写面试官可能会问“底层是怎么实现的”所以切片法适合工程临时数组法适合讲解。3.4 Go 实现make、copy 和 append 的注意事项Go 的惯用写法func rotate(nums []int, k int) { n : len(nums) if n 0 { return } k ((k % n) n) % n temp : make([]int, n) for i : 0; i n; i { temp[(ik)%n] nums[i] } copy(nums, temp) }有一个小细节make([]int, n)会初始化 n 个零值元素所以后面的赋值是直接覆盖没问题。如果用var temp []int然后append就要注意初始长度。copy(nums, temp)是内建函数目标切片和源切片长度可以不同它拷贝 min(len(dst), len(src)) 个元素。这里长度相同安全。Go 的切片本身就是引用类型但函数内的nums[i] ...能修改底层数组nums temp却不会影响外部所以一定要用copy或者循环赋值。3.5 各写法的共性思考不管什么语言算法骨架完全一致取模、建临时数组、循环赋值、拷贝回去。区别只在于语法糖和内存管理方式。我建议至少掌握两种语言的写法因为面试官可能会让你用自己最熟的语言写但思路必须能迁移。一个额外提醒在 C/C/Java/Go 里如果 k 很大k % n这一步可以有效避免整数溢出在 Python 里整数无限大不会溢出但取模依然必要因为不取模数组访问会越界。4. 我在实际提交中反复踩过的坑边界、取模与数组越界4.1 忘记对 k 取模导致的诡异结果我第一次提交这个题的临时数组解法时写的是temp[(i k) % n] nums[i];k 没有提前取模表面看也能过因为(ik)%n仍然能算出正确下标。但当时我遇到一个测试用例是nums[1,2], k3手动推导i0 - 3%21i1 - 4%20结果 temp [2,1]正确。所以这个写法不算错。但后来我改成先取模再算下标纯粹是因为代码可读性和安全性更好。如果 k 很大比如k 2147483647在某些语言里i k可能溢出成负数负数取模结果还是负数数组访问就越界了。所以“先取模”和“后取模”在大多数测试用例下等价但在极端输入下有本质区别。4.2 数组长度为 0 和长度为 1 的边界长度为 0 的数组任何轮转都没意义。如果你在没判断长度的情况下执行k % n会直接除零异常。长度为 1 的数组k 随便多大轮转后还是原样。有经验的刷题者会在函数开头就写上if (nums null || nums.length 1) return;顺手连空引用也一并处理了。这个习惯在面试中很加分因为你展示了对异常输入的警觉。4.3 把临时数组的大小写成 k导致下标越界这个错误我见过很多次。有同学想“只需要保存后面 k 个元素”于是写int[] temp new int[k]然后想把前 n-k 个元素往后挪。这不是临时数组法是另一种思路但很容易和临时数组法混淆。临时数组法要求“完整等长数组”因为每个元素都要在新数组里占一个位置。如果你只开 k 大小的数组你就必须额外处理哪些元素需要移动逻辑就复杂了。反正空间复杂度都是 O(n)不如开满省心。4.4 原地数组复制时用错引用在 Python 里nums temp不会修改原列表在 Java 里nums Arrays.copyOf(temp, n)同样不会修改调用者传入的数组引用。要原地修改必须逐元素赋值或者用系统拷贝 API。这个坑在本地调试时很难发现因为你在函数内部打印nums看着是对的但回到 main 函数再打印发现没变。遇到这种情况别怀疑算法先检查“到底改没改到原数组”。4.5 测试用例设计别只验证题目的例子做了一个小时的题最后提交却超时或越界很多情况下是因为自测用例太单一。我建议至少测这几组数组长度为 0、1。k 等于 0、等于 n、等于 n 的倍数。k 是负数如果题目允许。数组元素包含重复值、负值、最大值最小值。n 为奇数/偶数。特别是 k 等于 n 的倍数时如果提前取模一切正常如果不取模虽然结果也对但总会多跑几遍无意义循环临时数组法受影响不大其它解法可能因为循环链判断错误而出问题。4.6 临时数组法和“反转法”的坑别混在一起说到轮转数组很多资料会同时提到三种解法临时数组法、反转法、环状替换。这三种解法的边界处理和陷阱完全不同。临时数组法的坑主要在“引用传递”和“取模”反转法的坑在“反转三段的位置”环状替换的坑在“需要记录起始点和计数”。如果你在同一个面试里先写了临时数组法被追问“能不能优化”再写反转法请务必在脑子里切换到另一套逻辑。我见过有人把临时数组法的(ik)%n硬套到反转法里结果自然是错的。5. 临时数组法 vs 反转法 vs 环状替换什么时候该选谁5.1 三种解法核心思想概览临时数组法我们已经很熟悉了。其余两种我简单概括一下反转法先把整个数组反转再反转前 k 个再反转后 n-k 个。利用了反转的可逆性质原地完成时间 O(n)空间 O(1)。环状替换从某个起点开始把元素放到它该去的位置被替换的元素继续放到下一个位置形成若干条环。每移动一个元素就计数直到所有元素移动完时间 O(n)空间 O(1)。用一个表格对比解法时间复杂度空间复杂度是否原地代码可读性出错点临时数组法O(n)O(n)否高引用传递、取模反转法O(n)O(1)是中反转边界、k 为 0环状替换O(n)O(1)是低环的计数、gcd 推理5.2 反转法为什么是面试官最想听的优化反转法的核心代码特别短reverse(nums, 0, n-1) reverse(nums, 0, k-1) reverse(nums, k, n-1)前提是先k k % n。原理是整体反转后数组元素完全倒序然后再分别反转两段就能让后 k 个元素回到头部。很多人不理解为什么三次反转能实现轮转其实可以类比一串珠子先整体翻转相当于把珠子顺序倒过来再把前一段和后一段各自翻转相当于把原来最后一段“拧”到开头。这个解法的空间优势很明显但有一个隐藏的边界如果 k0第二段反转的起点和终点重合reverse(nums, 0, -1)之类实现反转函数时要能正确处理空区间。另外反转法对负数 k 的处理不如临时数组法直观需要先统一 k 的符号。5.3 环状替换的 tricky 点为什么不能只循环一次环状替换是最容易写错的原地解法。它的基本思路从下标 0 开始把 nums[0] 移到下标(0k)%n再把原来那个元素移到它的目标位置如此循环直到回到起点。然后再从下标 1 开始重复这个过程。但问题来了如果 n 和 k 不互质可能会出现多个环。比如n6, k2从 0 出发0 - 2 - 4 - 0只处理了偶数下标奇数下标永远不会被访问。所以必须用一个计数器统计已移动元素个数当等于 n 时停止。这是环状替换最容易错的地方。相比之下临时数组法完全不需要考虑这些因为新数组的每个位置都是干净的不存在覆盖问题。5.4 实际工程与面试场景的选型建议结合我的实际经验给你一个选型策略如果面试官没有明确要求 O(1) 空间优先写临时数组法快速、稳定、易解释。如果追问“能不能不用额外空间”立刻切换反转法因为原理简单且代码短。如果面试官非要你写环状替换一般是想考察你对“循环链”的理解写之前先想清楚计数器。在真实业务代码里我反而更少用原地修改因为原地修改会改变入参容易引发调用方预期之外的副作用。临时数组法返回一个新数组或者拷贝回原数组语义更清晰。所以刷题归刷题工程归工程。6. 从这道题延伸出去轮转数组的变体与真实应用6.1 左轮转与右轮转的相互转换很多场景下你会遇到“左轮转 k 位”的描述。左轮转 k 位等价于右轮转n - k % n位。比如[1,2,3,4,5]左转 2 位得到[3,4,5,1,2]右转 3 位也能得到同样结果。这个转换在写代码时很实用不管题目怎么描述先统一成右轮转然后继续用临时数组法。如果面试官问“为什么能转换”你可以用数组下标映射解释左转 k 的新下标是(i-kn)%n右转 n-k 的新下标是(in-k)%n两者在模 n 意义下完全相同。6.2 二维数组/矩阵的轮转增强版的临时数组法轮转数组的思想可以推广到二维矩阵旋转。比如顺时针旋转 90 度每个元素(i, j)会到(j, n-1-i)。如果你不想原地旋转完全可以开一个同样大小的新矩阵逐元素映射。这就是临时数组法在二维场景的直接应用。我曾在一个图像处理 Demo 里处理过图片旋转当时用的就是临时矩阵法。虽然内存翻了一倍但代码写起来非常清晰后续加滤镜、裁剪也方便。真要做高性能图像处理才会考虑原地旋转的分块算法。6.3 循环队列与滚动数组轮转思想的工程化轮转数组的本质是“环形下标”。这个概念在很多底层数据结构里都会出现循环队列的队头队尾指针移动时都要对容量取模滚动日志文件、环形缓冲区、滑动窗口的最大值等问题底层都是同一套取模逻辑。所以做这道题的价值不只是背一个(ik)%n而是理解“环形下标”这个思维模型。以后遇到“数据流持续写入、只保留最近 N 条”的需求你自然会想到用固定大小数组加头尾指针而不是反复申请新数组。6.4 要求返回新数组而非原地修改时有些变体题不会要求你原地修改而是直接返回一个新数组。这时临时数组法的代码可以更简洁直接把元素放到新数组的下标(ik)%n返回新数组。不需要第二段拷贝逻辑。我个人在写这种版本时会顺手把边界情况也处理掉比如返回空数组而不是 null。面试时“返回什么”一定要先和面试官确认避免用完你写的函数后发现原数组没变或者返回值不符合预期。6.5 一道题学到什么程度算“学透了”最后说说我自己衡量是否掌握一道题的标准。不是看一眼题解然后默写而是能做到以下几点不看任何参考十分钟内写出临时数组法。能说出k k % n的必要性并举出极端例子。能流畅写出反转法并说明为什么三次反转是对的。知道环状替换需要计数器能解释 gcd 的作用。能把这道题和循环队列、矩阵旋转联系起来。如果这些都能做到那么这道题对你来说就不只是一个题而是一个可以迁移的思维工具。刷题最怕的是背题解最值得的是理解“为什么”。临时数组法作为最朴素的解法正是理解这道题最合适的起点。每次写它我都会提醒自己先搞明白要到哪里去再决定怎么去。