LeetCode 189旋转数组：三次反转法与原地算法详解-北京尧图网络

关于力扣189题我印象挺深。这道题表面叫“旋转数组”考察的却是对数组遍历、下标映射和边界条件的综合掌控被收进热题100不是没道理。如果你最近在准备算法面试或者只是想把基础数据结构刷扎实这道题值得花半小时好好拆一遍因为它站在一个很尴尬的位置——说简单吧暴力解法谁都能写说难吧好多人卡在“原地”和“O(n)”两个词上面试一紧张就容易翻车。这篇文章不打算只贴解法代码。我会把题目背后真正需要理解的几个点掰开来讲比如为什么第三次反转是对的步数 k 超出数组长度时到底发生了什么以及你写的循环移位代码在真实工程里有没有隐藏雷区。这些都是面试中容易被追问、日常刷题时又不太有人讲的细节。1. 先把题目和热题100的定位搞清楚题目本身一句话就能说清楚给定一个数组将数组中的元素向右移动 k 个位置其中 k 是非负数。示例给的是[1,2,3,4,5,6,7]和k 3期望结果是[5,6,7,1,2,3,4]。理解这个结果只需要一个动作把数组从中间某个位置“切断”然后把两段互换位置。但热题100把它放在数组分类里考察的显然不只是“会不会调用库函数”。这道题真正想验证的是你能不能看出“旋转”在数学上等价于某种反转操作组合你能不能处理 k 对 n 取模这类边界逻辑你能不能写清楚“原地旋转”而不用额外数组控制住空间复杂度。我在实际面试别人或者被人面试的时候这题被问到的变体非常多有的要求不能使用额外数组有的要求 k 可能是负数代表左移有的会直接让你实现循环移位数据量还不小。要是只背了一道题的答案稍微变一下条件就懵了。所以我更建议把它当成一个“数组操作思维训练题”来对待而不只是一个需要记忆的标准答案。理解了它背后的下标运算后面再做那些翻转字符串、轮转链表、循环队列之类的题目都能少吃点苦头。2. 几种标准解法的演进过程与取舍2.1 最直觉的暴力法每次移动一个位置暴力解法是大多数人看到题目后的第一反应循环 k 次每次把整个数组向右移动一位最后的元素放到开头。代码非常简单两层循环就完事。public void rotate(int[] nums, int k) { int n nums.length; k % n; for (int i 0; i k; i) { int last nums[n - 1]; for (int j n - 1; j 0; j--) { nums[j] nums[j - 1]; } nums[0] last; } }这个解法的时间复杂度是 O(k*n)空间复杂度是 O(1)。看起来挺无脑实际测试场景里如果 n 是十万级别、k 又是五万跑起来就很痛苦。但它作为第一直觉是合理的面试时你可以先说出来表明你知道问题是什么然后再给出优化版本。我提醒一点题目给的 k 可能比数组长度大很多比如 n 是 7、k 是 10那向右移动 10 位其实等价于向右移动 3 位。所以暴力也好、后续高级算法也好第一步永远都是k % n否则性能会崩。2.2 用额外数组空间换时间代码最短额外数组法是我见过所有答案里最容易写对的解法。逻辑就是遍历原数组把每个元素放到新数组的(i k) % n位置最后再拷贝回原数组。public void rotate(int[] nums, int k) { int n nums.length; 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); }这个解法的核心思想是用下标映射代替物理移动。你把“旋转”看成了一种排列变换每个位置上的元素去哪儿由(原下标步长) 对长度取模决定。时间 O(n)空间 O(n)。如果题目没有“原地”限制这绝对是最稳妥的写法因为绝对不会因为边界条件翻车。System.arraycopy是 Java 里拷贝数组的高效原语底层走的是 native 内存操作不要自己再写一层 for 循环去覆盖既慢又容易错。面试时如果时间紧先写这个版本保底非常合理。但你得能接得住追问空间复杂度能不能降下来这就会引导到下一步。2.3 三次反转法原地旋转的标准答案三次反转法是我最推荐掌握的核心解法。思路一句话先反转整个数组再反转前 k 个元素最后反转后 n-k 个元素。拿[1,2,3,4,5,6,7]、k3 举例反转整个数组[7,6,5,4,3,2,1]反转前 3 个[5,6,7,4,3,2,1]反转后 4 个[5,6,7,1,2,3,4]结果和题目要求完全一致。为什么这样是对的从数学上看数组的左右旋转本质上可以分解成原序列的子段逆序再组合。严谨点的证明思路是数组反转操作是幂等的两次反转同一个区间会回到原样而三次反转恰好在 O(n) 时间内实现了“元素整体平移 k 位”的效果。实现代码时有个容易错的地方——反转的区间边界。前 k 个元素的下标范围是[0, k-1]后一半是[k, n-1]。很多人会把 k 和下标搞混明明 k3 却反转[0, 3]结果把头 4 个元素反转了。这里我建议你写一个统一的reverse(nums, start, end)辅助函数闭区间处理测试样例时多跑几组边界数据。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 start, int end) { while (start end) { int temp nums[start]; nums[start] nums[end]; nums[end] temp; start; end--; } }三次反转法的时间复杂度 O(n)空间 O(1)是“原地”要求下的最优解也是这题在 LeetCode 官方题解和各类面试答案里最常见的版本。你需要把每一步的区间写清楚尤其是 k 等于 0 或者 k 等于数组长度的时候算法要能安静地走完而不报错。2.4 循环移位法最酷但最容易被绕晕的写法循环移位法也叫 Juggling Algorithm核心逻辑是从某个起点出发把元素依次放到它应该在的位置上直到回到起点完成一个环。然后换下一个起点继续直到所有元素都处理过。举个例子数组长度 n6k2那么从下标 0 出发0 的元素去 22 的元素去 44 的元素去 0这就形成了一个闭环再从下标 1 出发1 去 33 去 55 回 1第二个环也闭合。两次环就把所有元素覆盖了。这种方法的时间复杂度也是 O(n)空间 O(1)而且它揭示了旋转操作和“循环置换”之间的关系。它的难点在于你需要确定环的个数和每一个环的起点。环的数量等于 n 和 k 的最大公约数如果你搞不清这个数学关系外层循环的次数就会算错导致一部分元素被漏掉或者被重复覆盖。public void rotate(int[] nums, int k) { int n nums.length; k % n; if (k 0) return; int count gcd(n, k); for (int start 0; start count; start) { int current start; int prev nums[start]; do { int next (current k) % n; int temp nums[next]; nums[next] prev; prev temp; current next; } while (current ! start); } } private int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; }这个解法面试中能写出来是加分项它说明你对数学结构和数组下标有更深的理解。但如果你没把环的数量算清楚do-while 循环容易变成死循环。我建议平时练习时把三种解法都写一遍尤其是这一种写熟悉之后你再回头做别的轮转类题目思路会开阔很多。3. 边界条件与工程级的细节处理刷题和写工程代码有一个共性逻辑再漂亮边界条件没覆盖全就是白搭。旋转数组这道题的边界条件虽然不多但每一个都可能让你的代码在隐藏用例上挂掉。3.1 k 的取值边界k 可能是 0、可能是负数有些变体要求、可能远大于数组长度。不论哪种先执行k % n永远是最安全的第一步。这样处理之后k 一定落在[0, n-1]的区间内后续所有逻辑都建立在统一前提上。尤其注意 k 等于 0 的情况。如果你用循环移位法k0 时 count gcd(n,0) n会白白执行 n 次循环虽然不报错但效率很差。所以很多优秀写法第一行就判断if (k 0) return;宁可多写一次判断也不要让逻辑走无谓的路。对于 k 为负数的变体处理方式是把负数先加 n 转成正数k (k % n n) % n。这个写法是 Java 里处理负数取模的标准姿势因为 Java 的%运算结果符号跟被除数一致直接取模再使用是不安全的。3.2 数组长度特殊值数组长度为 0 或者长度为 1 的时候旋转没有任何意义。这两种情况下任何 k 值都不该改变数组内容。我见过不少人在空数组上直接执行反转逻辑reverse方法里 start0、end-1while 条件 start end 不成立侥幸不报错。但有些写法用了end n - 1再去下标访问就会抛数组越界。所以一个简单的防御性判断很有必要if (nums null || nums.length 2) { return; }这不是炫技而是工程习惯。算法题里多写一行防御面试官不会觉得你啰嗦反而会觉得你考虑周全。3.3 原地操作与额外空间的权衡热题100原题的要求其实没有强制“原地”但时间复杂度要求 O(n)。这意味着额外数组法也是合法的。但如果面试官追问“能不能不用额外空间”你要立刻给出三次反转法。这里有个工程上的思考角度原地操作不一定更好。在真实系统的代码里如果你不担心内存压力额外数组法的代码更易读、更不易错。LeetCode 的判题环境里空间差距不明显但生产环境里一个亿级数组多开一倍空间GC 压力和内存占用都是问题。所以算法面试中强调“原地”确实有它现实层面的意义不只是为了难为人。我在实际编码时有个习惯无论哪种解法先画一遍小样例的模拟过程确认每一步数组内容符合预期再写代码。比如 n7, k3 这种经典用例三次反转每一步是什么结果心里有数了再下手错概率能降低一半。4. 轮转类问题的通用方法论旋转数组只是轮转类问题的一个代表。这类问题的深层逻辑可以总结成一个通用模板任何循环移位问题先确定周期再确定移动方向最后确定遍历范围。周期就是数组长度或者链表的环长度。移动方向决定下标计算是加还是减。遍历范围决定你是处理整个结构还是一个子区间。举个例子如果把数组改成字符串要求把字符串左移 k 位解法几乎一样只是反转函数接收的是字符数组。如果把数组改成单链表要求整体轮转那就需要先遍历一遍求长度再把尾节点连到头节点形成环移动到目标位置后断开。这种变体能明显拉开“真懂”和“背题”的人之间的距离。还有一类常见变体是“旋转矩阵”。给定一个二维矩阵要求顺时针旋转90度。它和旋转数组的关系在于矩阵旋转可以看成先按行反转、再沿对角线对称交换。这个思路某种程度上就是从一维三次反转扩展出来的多维版本。如果你能把一维的旋转吃透二维的旋转学起来也快得多。所以我说这道题值得反复做三遍第一遍看懂题解第二遍独立写出三次反转法第三遍尝试循环移位法并自己解释为什么环的个数是最大公约数。每一遍的收获完全不同。5. 常见问题与排查技巧实录这节列几个我实际见过、也常被问到的坑。这些坑在 LeetCode 的评论区被反复提过写成速查表方便你自查。场景症状原因解决办法没执行k % n大数据量下超时k 太大导致无效循环先取模保证 k nk 0数组左移Java 取模结果为负k (k % n n) % n;reverse 区间写错结果部分正确闭区间开区间混淆start 和 end 都写有效下标统一闭区间数组长度为 1正确答案但方法异常反转函数未对边界防御长度小于 2 直接 return循环移位死循环外层循环次数算错环数量 gcd(n,k)先算 gcd 再写 do-while额外数组法内容未覆盖原数组没变化忘了拷贝回原数组用 System.arraycopy 或手动覆盖除了这些可预见的坑我再分享一个实战经验提交之前一定自己在本地跑几组测试用例。至少包含数组长度 1、2、7k 分别取 0、1、n、n1、n-1、n2 这些值。你会发现很多边界 bug 在没有完整测试集的情况下根本暴露不出来。还有一次我印象特别深是给一个数据集的轮转需求写本地脚本。当时我用的是循环移位法但数据集巨大k 大约是 1.2 亿。因为一开始忘了取模CPU 直接跑满等了十几分钟没出来。后来改成先取模瞬间解决问题。从那之后我养成了肌肉记忆任何轮转类逻辑第一步永远先对长度取模这比任何优化都重要。6. 对实际开发的可借鉴之处很多人觉得算法题跟日常工作离得远但旋转数组这种操作在工程里真的会出现。最常见的是日志系统里的“环形缓冲区”。当缓冲区满了之后新数据要覆盖最旧的数据本质就是一种带固定窗口的轮转。再比如任务调度系统里一组固定长度的任务队列定期把过期任务移到末尾也是旋转思想的应用。图像处理里的像素平移、拼图游戏的滑块移动底层都离不开数组下标映射。另一个我能想到的典型场景是缓存更新策略里的环形淘汰算法。服务端维护一个固定大小的循环数组按权重轮询更新每轮从不同起始位置开始覆盖这和旋转数组的下标映射是一模一样的思路。理解了 LeetCode 189 题的取模逻辑你写这类代码时就不容易在 index 计算上翻车。还有数据可视化里的“轮播数据窗口”每隔一段时间展示最近 N 个数据点新数据进来就把窗口向前推进一格。窗口的本质就是数组切片的平移而平移和旋转是同一家族的操作。所以在项目里看到对数组做位移、翻转、拼接的场景时你可以想一想它能不能用三次反转的框架来解。这种“迁移思维”比单纯记住一道题的答案有价值得多。7. 总结几种方法选型的直觉判断面试或者平常练习写哪一种解法取决于题目的附加条件我建议按这个逻辑来判断如果题目没要求原地直接写额外数组法因为最不容易错。如果要求原地且允许 O(n) 时间三次反转法是最稳妥的选择代码量短、理解门槛低。如果面试官还想看你对循环结构的理解你可以补充循环移位法但一定要把 gcd 的推导讲清楚。从时间复杂度和空间复杂度两个维度来看暴力法 O(kn) 时间、O(1) 空间只配作为思路铺垫额外数组法 O(n) 时间、O(n) 空间是工程最稳妥三次反转法 O(n) 时间、O(1) 空间是算法面试最优循环移位法 O(n) 时间、O(1) 空间是理解最深但最容易写错。我个人的建议是优先掌握三次反转法把它写到闭着眼睛都能默写的程度。循环移位法作为进阶内容学有余力再研究。暴力法和额外数组法用来帮助理解题目而不是作为最终答案。这三种解法的代码风格也有讲究。像 Java 里System.arraycopy、Arrays工具类的使用Python 里的切片赋值nums[:] nums[n-k:] nums[:n-k]都能有效降低代码出错率。不同语言的表达方式不一样但核心思想是一致的下标映射决定方向反转操作实现位移。我把这个题目反复练了几次之后最大的感受是算法题的解法之间不是互斥关系而是一条递进的认知路径。你从暴力法理解问题从额外数组法理解下标从反转法理解数学结构从循环移位法理解周期和置换。每走一步对这个问题的理解就深一层。如果你最近正好在刷热题100建议不要只追求“AC”而是每道题都把从朴素到最优的各种解法过一遍把边界条件和复杂度推导写清楚。这个过程积累的不是一个个孤立的答案而是一整套解决问题的分析框架。189题只是其中一站但它教给你的数组操作思维会跟着你走很远。

LeetCode 189旋转数组：三次反转法与原地算法详解

相关推荐

Linux下GT115x触摸屏驱动移植实战：从设备树到中断排查

解决虚拟机IP漂移：手把手配置静态IP（CentOS/Ubuntu）

open-code-review：构建自动化代码评审工作流

更多资讯

2026图文带货必备：五款AI去水印与图文排版工具实测

Windows下Docker部署openclaw：从环境配置到迁移实战

本地化AI工作流：OpenAI协议兼容的私有化部署实践

校园食堂订餐系统毕业设计：Java+Spring Boot+MySQL完整实战指南

MySQL事务底层机制：从redo/undo到MVCC与锁的实践解析

大模型重塑移动端自动化测试：从痛点破局到智能落地实践

今日更新

悟空开源无代码平台实战：从实体建模到应用设计避坑指南

基于.NET9的多租户权限系统：数据权限与动态API落地实践

场地预约小程序毕设实战：SSM+微信小程序+MySQL数据库设计到避坑

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？