空间原地修改全解)
这些年刷LeetCode Hot 100第189题轮转数组我一直觉得是个被低估的题目。它挂着Medium的牌子实际难度卡在Easy到Medium之间但每次面试前拿它热身都能让我冷静下来数组下标映射、取模、原地修改、双指针几个最基础的能力点全在这一道题里。我第一次刷的时候只会写O(n*k)的暴力解法被大用例直接教做人后来学会了额外数组解法又在能不能O(1)空间原地完成上卡了很久。这道题适合刚入门的人建立数组操作手感也适合准备跳槽的人当作复杂度分析的复习样本。今天我把这道题从暴力到最优全部拆开顺便把我踩过的坑一并交代清楚。1. 先把题目彻底讲明白1.1 题意拆解什么叫向右轮转k个位置题面很简单给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。注意这里说的是轮转而不是普通的平移区别就在于越界元素要绕回到数组开头相当于数组被看成了一个环。举个例子nums [1,2,3,4,5,6,7]k 3期望结果是[5,6,7,1,2,3,4]。手推一遍过程右移1位[7,1,2,3,4,5,6]右移2位[6,7,1,2,3,4,5]右移3位[5,6,7,1,2,3,4]理解每个元素最终去哪有个更直观的方式原数组下标i的元素最终会移动到下标(i k) % n的位置n是数组长度。这个取模操作是整个题目的灵魂后面所有解法其实都是围绕它展开的。生活化类比想象一队人排成一圈喊向右走三步站在队尾的人会绕回队头而不是掉出队伍。轮转数组就是这个圈被拉成了一条直线后的效果。1.2 边界条件这些坑往往比算法本身更致命很多人在LeetCode上提交失败不是算法思路错了而是忽略了极端情况。轮转数组的边界条件我整理了这么几类空数组nums []任何操作都不该报错取模时要注意避免对0取模。单元素数组nums [5]不管k多大结果都是它本身。k 0不需要做任何操作。这个看似简单但三次翻转法如果不小心处理切片或区间边界可能出现end start的情况。k n题目里k可能远大于数组长度。比如nums长度为3k 5轮转5次等价于轮转2次因为转一整圈等于没转。正确做法是k % n。k是n的整数倍等价于k 0数组完全不变。我建议拿到任何数组题先默认把n 0、n 1、k 0这三个用例在心里过一遍。很多隐藏bug都是在这三种情况里暴露的。2. 从暴力解到额外数组先把基础打稳2.1 暴力解法最容易想但最不该直接交上去暴力思路一句话重复执行整体右移一位操作k次。每次右移一位时把最后一个元素存下来再把前面所有元素依次向后移动一个位置最后把存下来的元素放到开头。def rotate(nums, k): n len(nums) if n 0: return 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)空间复杂度是O(1)。当k接近n时最坏情况是O(n^2)级别。LeetCode的测试数据规模通常到10^5甚至更大O(n * k)直接超时我第一遍刷就是在这里被教育了。这个解法唯一的价值在于验证思路你确认了每次移动一位是可行的只是太慢。面试的时候可以提一句暴力法能过小数据但大数据会超时然后立刻优化这比什么都不说直接写最优解更显得思路完整。2.2 额外数组解法用空间换时间先保证正确既然暴力慢最自然的优化就是不再一遍遍挪而是直接计算每个元素最终要去哪原下标i的元素放到(i k) % n一次遍历完成。def rotate(nums, k): n len(nums) ans [0] * n for i in range(n): ans[(i k) % n] nums[i] nums[:] ans拿前面的例子验证nums [1,2,3,4,5,6,7]k 3(1 3) % 7 4也就是说数字2原下标1最终到下标4的位置。整个过程每个元素只移动一次所以时间复杂度O(n)但需要额外的一个长度为n的数组空间复杂度O(n)。这里必须提一个Python特有的坑如果你写nums ans函数执行完之后外部变量指向的还是旧数组因为nums这个局部变量被重新绑定了。必须写nums[:] ans也就是原地把新数组内容覆盖到旧数组内存区域里才能真正修改调用方的数组。这个坑我后面专门再讲。额外数组解法在面试中作为正确性优先的方案非常合适。它把复杂问题变成一行映射公式代码几乎不可能写错非常适合作为答题的第一步。3. 面试官最想听的O(1)空间解法三次翻转3.1 三次翻转的核心思想与数学推导额外数组解法已经很舒服了但面试官通常会紧接着问一句能不能不用额外空间这时候轮转数组的经典方案——三次翻转——就该登场了。思路是把数组分成两部分前n - k个元素作为一块后k个元素作为另一块。目标是把后一块整体搬到前面。三次翻转的做法翻转整个数组。翻转前k个元素。翻转后n - k个元素。用[1,2,3,4,5,6,7]和k 3走一遍原始数组[1,2,3,4,5,6,7]整体翻转[7,6,5,4,3,2,1]翻转前3个[5,6,7,4,3,2,1]翻转后4个[5,6,7,1,2,3,4]结果正确。为什么这么做能成立用符号推导更清楚。设数组为A B其中A长度为n - kB长度为k。整体翻转得到reverse(B) reverse(A)。再翻转前k个也就是reverse(reverse(B))变回B翻转后n - k个reverse(reverse(A))变回A。最终得到B A恰好是轮转目标。这道推导我建议每个刷题的人都能当场讲出来它证明你不是背答案而是真的理解了翻转为什么能完成部分整体搬家这件事。面试时讲到这一层印象分会明显不一样。3.2 手写reverse的细节与代码模板翻转操作最好手写不要过度依赖语言自带的库函数。手写双指针翻转是最稳的def reverse(nums, left, right): while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 def rotate(nums, k): n len(nums) if n 0: return k % n reverse(nums, 0, n - 1) reverse(nums, 0, k - 1) reverse(nums, k, n - 1)写的时候有三个细节都是我实际踩过或见别人踩过的第二段翻转的区间是[0, k - 1]第三段是[k, n - 1]千万不要把第二段写成[0, k]否则会多翻一个元素结果全错。k取模后再用。如果k 0第二段会变成reverse(nums, 0, -1)由于while left right不成立直接跳过不报错但心里要清楚这是空操作。翻转函数里用while而不是for因为边界位置是动态变化的for i in range(left, right)没法简洁地实现两端交换。C和Java写法类似只是交换元素时用临时变量。C可以直接用std::reverseJava的数组没有现成的Collections.reverse可用那是给List用的老老实实写双指针。三次翻转的价值在于时间复杂度O(n)空间复杂度O(1)而且代码只有十几行。这是面试中最稳妥的最优解答案。4. 环状替换法另一个原地方案4.1 环的起点与环的数量gcd是关键除了三次翻转还有另一个原地解法叫环状替换。核心思路很直接既然元素i要去(i k) % n那就顺着这个链条把元素依次放到该去的位置类似于链表里按顺序搬移。拿nums [1,2,3,4,5,6,7]k 3举例。从下标0出发下标0的元素1放到下标3先把下标3原有的4存起来再把1放进去下标3的元素4应该放到下标6下标6原有的7存起来放入4下标6的元素7应该放到下标2继续走下去2 - 5 - 1 - 4 - 0最后回到起点0。这一圈走下来刚好把所有7个元素都放到了正确位置因为n 7和k 3的最大公约数是1整个数组只有一个环。但并不是所有数组都只有一个环。比如n 6k 2gcd(6, 2) 2这个数组就分成两个环0 - 2 - 4 - 0和1 - 3 - 5 - 1。如果只从0出发处理完三个元素就回到起点剩下三个元素压根没被碰过。所以环状替换必须记录一共处理了多少个元素每移动一个元素计数加1直到计数等于n才能确认所有环都被处理完毕。4.2 实现代码与两个关键变量def rotate(nums, k): n len(nums) if n 0: return k % n count 0 start 0 while count n: current start prev nums[start] while True: nxt (current k) % n temp nums[nxt] nums[nxt] prev prev temp current nxt count 1 if current start: break start 1这里有三个必须记住的变量prev保存上一个位置的元素它要被放到当前位置。current当前正在处理的环的游标。count全局计数器保证所有环都被遍历防止死循环。我写环状替换犯过的错误第一个是忘了在循环开头做k % n导致nxt计算后越界第二个是忘了count 1结果while count n永远成立直接死循环第三个是把start 1放在while True内部导致同一个环被反复处理。环状替换的时间复杂度也是O(n)空间O(1)但代码比三次翻转更容易写错日常面试我更推荐优先讲三次翻转。环状替换的价值在于当面试官追问你还有别的原地方案吗时你能拿出它。5. 常见问题与面试实战经验5.1 高频Bug速查表错误类型具体表现原因与修正忘记取模k远大于n时结果错误或越界在一切操作前先执行k % n翻转区间边界差一第二段写成[0, k]记住区间是[0, k-1]和[k, n-1]Python切片不是原地修改调用方数组没变用nums[:] ...别用nums ...环状替换死循环程序无法结束检查count是否自增start是否在外层循环递增空数组取模报错n 0时k % n异常函数开头先判断if n 0单元素数组多此一举结果本身就对但代码可能越界特判或依靠k % n后自然处理这张表是我刷题过程中真实遇到过的每一行都对应一次因细节丢分的经历。强烈建议在提交前对照检查一遍。5.2 我踩过的坑Python原地修改的底层逻辑Python里这个大坑值得单独再说一次。nums rotated_list在函数内部只是把局部变量nums指向了新对象外部传入的数组引用一点没变。我最早写轮转数组时在函数内用nums ans然后自信地跑测试发现结果完全没变化排查了半天。要用切片赋值nums[:] ans它会调用对象的__setitem__把原对象内部内存逐位覆盖成新内容。类似道理也适用于其他Python解题场景只要题目要求原地修改传入数组你就得时刻提醒自己究竟是重新绑定变量还是真正修改内存内容。顺带提一个常见疑问nums[:] nums[-k:] nums[:-k]算不算原地严格说nums[-k:] nums[:-k]这个拼接操作会构造一个新列表空间复杂度是O(n)所以它是额外数组解法的另一种写法不属于O(1)空间。但它代码最短如果面试允许可以在讲完最优解后补充说如果允许额外空间还可以用切片一行完成展示你熟悉语言特性。5.3 面试答题节奏从暴力到最优的递进话术面试里遇到这道题不建议一上来就甩三次翻转。我的习惯节奏是这样的先复述题意确认k是否可能大于数组长度、是否允许额外空间。这一步体现出你注意边界条件。给出暴力解法说清楚它O(n*k)的问题。主动提出额外数组解法O(n)时间O(n)空间讲解下标映射(i k) % n。面试官追问能不能降低空间顺势讲三次翻转并把AB - reverse(B)reverse(A) - BA的推导写出来。如果面试官继续深挖再给出环状替换强调gcd决定的环数量和count计数器。这套递进既能让面试官看到你从朴素到优化的完整思维路径也能避免直接写结论导致背题的观感。这道题的难点其实不在于想出最优解而在于能不能在紧张的环境下一次写对边界条件。最后讲一点个人体会。轮转数组看起来只是Hot 100里一个不太起眼的Medium但它是极少数我能用同一道题讲清楚暴力优化、取模边界、原地修改、多方案对比四件事的题目。我后来每次面试前都会把它当作热身题不是为了刷熟练度而是为了让自己重新进入先想边界、再想复杂度、最后动手写的答题状态。如果你正在刷题这道题值得多写几遍——第一遍用额外数组保证正确第二遍用三次翻转压缩空间第三遍用环状替换检验自己对循环不变量的理解。三遍下来数组类题目的很多通用套路你基本就摸透了。 
长河君 · 2026/10/10 6:45:22 · 阅读 1.2k 轮转数组从暴力到三次翻转：数组操作与O(1)空间原地修改全解
这些年刷LeetCode Hot 100第189题轮转数组我一直觉得是个被低估的题目。它挂着Medium的牌子实际难度卡在Easy到Medium之间但每次面试前拿它热身都能让我冷静下来数组下标映射、取模、原地修改、双指针几个最基础的能力点全在这一道题里。我第一次刷的时候只会写O(n*k)的暴力解法被大用例直接教做人后来学会了额外数组解法又在能不能O(1)空间原地完成上卡了很久。这道题适合刚入门的人建立数组操作手感也适合准备跳槽的人当作复杂度分析的复习样本。今天我把这道题从暴力到最优全部拆开顺便把我踩过的坑一并交代清楚。1. 先把题目彻底讲明白1.1 题意拆解什么叫向右轮转k个位置题面很简单给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。注意这里说的是轮转而不是普通的平移区别就在于越界元素要绕回到数组开头相当于数组被看成了一个环。举个例子nums [1,2,3,4,5,6,7]k 3期望结果是[5,6,7,1,2,3,4]。手推一遍过程右移1位[7,1,2,3,4,5,6]右移2位[6,7,1,2,3,4,5]右移3位[5,6,7,1,2,3,4]理解每个元素最终去哪有个更直观的方式原数组下标i的元素最终会移动到下标(i k) % n的位置n是数组长度。这个取模操作是整个题目的灵魂后面所有解法其实都是围绕它展开的。生活化类比想象一队人排成一圈喊向右走三步站在队尾的人会绕回队头而不是掉出队伍。轮转数组就是这个圈被拉成了一条直线后的效果。1.2 边界条件这些坑往往比算法本身更致命很多人在LeetCode上提交失败不是算法思路错了而是忽略了极端情况。轮转数组的边界条件我整理了这么几类空数组nums []任何操作都不该报错取模时要注意避免对0取模。单元素数组nums [5]不管k多大结果都是它本身。k 0不需要做任何操作。这个看似简单但三次翻转法如果不小心处理切片或区间边界可能出现end start的情况。k n题目里k可能远大于数组长度。比如nums长度为3k 5轮转5次等价于轮转2次因为转一整圈等于没转。正确做法是k % n。k是n的整数倍等价于k 0数组完全不变。我建议拿到任何数组题先默认把n 0、n 1、k 0这三个用例在心里过一遍。很多隐藏bug都是在这三种情况里暴露的。2. 从暴力解到额外数组先把基础打稳2.1 暴力解法最容易想但最不该直接交上去暴力思路一句话重复执行整体右移一位操作k次。每次右移一位时把最后一个元素存下来再把前面所有元素依次向后移动一个位置最后把存下来的元素放到开头。def rotate(nums, k): n len(nums) if n 0: return 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)空间复杂度是O(1)。当k接近n时最坏情况是O(n^2)级别。LeetCode的测试数据规模通常到10^5甚至更大O(n * k)直接超时我第一遍刷就是在这里被教育了。这个解法唯一的价值在于验证思路你确认了每次移动一位是可行的只是太慢。面试的时候可以提一句暴力法能过小数据但大数据会超时然后立刻优化这比什么都不说直接写最优解更显得思路完整。2.2 额外数组解法用空间换时间先保证正确既然暴力慢最自然的优化就是不再一遍遍挪而是直接计算每个元素最终要去哪原下标i的元素放到(i k) % n一次遍历完成。def rotate(nums, k): n len(nums) ans [0] * n for i in range(n): ans[(i k) % n] nums[i] nums[:] ans拿前面的例子验证nums [1,2,3,4,5,6,7]k 3(1 3) % 7 4也就是说数字2原下标1最终到下标4的位置。整个过程每个元素只移动一次所以时间复杂度O(n)但需要额外的一个长度为n的数组空间复杂度O(n)。这里必须提一个Python特有的坑如果你写nums ans函数执行完之后外部变量指向的还是旧数组因为nums这个局部变量被重新绑定了。必须写nums[:] ans也就是原地把新数组内容覆盖到旧数组内存区域里才能真正修改调用方的数组。这个坑我后面专门再讲。额外数组解法在面试中作为正确性优先的方案非常合适。它把复杂问题变成一行映射公式代码几乎不可能写错非常适合作为答题的第一步。3. 面试官最想听的O(1)空间解法三次翻转3.1 三次翻转的核心思想与数学推导额外数组解法已经很舒服了但面试官通常会紧接着问一句能不能不用额外空间这时候轮转数组的经典方案——三次翻转——就该登场了。思路是把数组分成两部分前n - k个元素作为一块后k个元素作为另一块。目标是把后一块整体搬到前面。三次翻转的做法翻转整个数组。翻转前k个元素。翻转后n - k个元素。用[1,2,3,4,5,6,7]和k 3走一遍原始数组[1,2,3,4,5,6,7]整体翻转[7,6,5,4,3,2,1]翻转前3个[5,6,7,4,3,2,1]翻转后4个[5,6,7,1,2,3,4]结果正确。为什么这么做能成立用符号推导更清楚。设数组为A B其中A长度为n - kB长度为k。整体翻转得到reverse(B) reverse(A)。再翻转前k个也就是reverse(reverse(B))变回B翻转后n - k个reverse(reverse(A))变回A。最终得到B A恰好是轮转目标。这道推导我建议每个刷题的人都能当场讲出来它证明你不是背答案而是真的理解了翻转为什么能完成部分整体搬家这件事。面试时讲到这一层印象分会明显不一样。3.2 手写reverse的细节与代码模板翻转操作最好手写不要过度依赖语言自带的库函数。手写双指针翻转是最稳的def reverse(nums, left, right): while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 def rotate(nums, k): n len(nums) if n 0: return k % n reverse(nums, 0, n - 1) reverse(nums, 0, k - 1) reverse(nums, k, n - 1)写的时候有三个细节都是我实际踩过或见别人踩过的第二段翻转的区间是[0, k - 1]第三段是[k, n - 1]千万不要把第二段写成[0, k]否则会多翻一个元素结果全错。k取模后再用。如果k 0第二段会变成reverse(nums, 0, -1)由于while left right不成立直接跳过不报错但心里要清楚这是空操作。翻转函数里用while而不是for因为边界位置是动态变化的for i in range(left, right)没法简洁地实现两端交换。C和Java写法类似只是交换元素时用临时变量。C可以直接用std::reverseJava的数组没有现成的Collections.reverse可用那是给List用的老老实实写双指针。三次翻转的价值在于时间复杂度O(n)空间复杂度O(1)而且代码只有十几行。这是面试中最稳妥的最优解答案。4. 环状替换法另一个原地方案4.1 环的起点与环的数量gcd是关键除了三次翻转还有另一个原地解法叫环状替换。核心思路很直接既然元素i要去(i k) % n那就顺着这个链条把元素依次放到该去的位置类似于链表里按顺序搬移。拿nums [1,2,3,4,5,6,7]k 3举例。从下标0出发下标0的元素1放到下标3先把下标3原有的4存起来再把1放进去下标3的元素4应该放到下标6下标6原有的7存起来放入4下标6的元素7应该放到下标2继续走下去2 - 5 - 1 - 4 - 0最后回到起点0。这一圈走下来刚好把所有7个元素都放到了正确位置因为n 7和k 3的最大公约数是1整个数组只有一个环。但并不是所有数组都只有一个环。比如n 6k 2gcd(6, 2) 2这个数组就分成两个环0 - 2 - 4 - 0和1 - 3 - 5 - 1。如果只从0出发处理完三个元素就回到起点剩下三个元素压根没被碰过。所以环状替换必须记录一共处理了多少个元素每移动一个元素计数加1直到计数等于n才能确认所有环都被处理完毕。4.2 实现代码与两个关键变量def rotate(nums, k): n len(nums) if n 0: return k % n count 0 start 0 while count n: current start prev nums[start] while True: nxt (current k) % n temp nums[nxt] nums[nxt] prev prev temp current nxt count 1 if current start: break start 1这里有三个必须记住的变量prev保存上一个位置的元素它要被放到当前位置。current当前正在处理的环的游标。count全局计数器保证所有环都被遍历防止死循环。我写环状替换犯过的错误第一个是忘了在循环开头做k % n导致nxt计算后越界第二个是忘了count 1结果while count n永远成立直接死循环第三个是把start 1放在while True内部导致同一个环被反复处理。环状替换的时间复杂度也是O(n)空间O(1)但代码比三次翻转更容易写错日常面试我更推荐优先讲三次翻转。环状替换的价值在于当面试官追问你还有别的原地方案吗时你能拿出它。5. 常见问题与面试实战经验5.1 高频Bug速查表错误类型具体表现原因与修正忘记取模k远大于n时结果错误或越界在一切操作前先执行k % n翻转区间边界差一第二段写成[0, k]记住区间是[0, k-1]和[k, n-1]Python切片不是原地修改调用方数组没变用nums[:] ...别用nums ...环状替换死循环程序无法结束检查count是否自增start是否在外层循环递增空数组取模报错n 0时k % n异常函数开头先判断if n 0单元素数组多此一举结果本身就对但代码可能越界特判或依靠k % n后自然处理这张表是我刷题过程中真实遇到过的每一行都对应一次因细节丢分的经历。强烈建议在提交前对照检查一遍。5.2 我踩过的坑Python原地修改的底层逻辑Python里这个大坑值得单独再说一次。nums rotated_list在函数内部只是把局部变量nums指向了新对象外部传入的数组引用一点没变。我最早写轮转数组时在函数内用nums ans然后自信地跑测试发现结果完全没变化排查了半天。要用切片赋值nums[:] ans它会调用对象的__setitem__把原对象内部内存逐位覆盖成新内容。类似道理也适用于其他Python解题场景只要题目要求原地修改传入数组你就得时刻提醒自己究竟是重新绑定变量还是真正修改内存内容。顺带提一个常见疑问nums[:] nums[-k:] nums[:-k]算不算原地严格说nums[-k:] nums[:-k]这个拼接操作会构造一个新列表空间复杂度是O(n)所以它是额外数组解法的另一种写法不属于O(1)空间。但它代码最短如果面试允许可以在讲完最优解后补充说如果允许额外空间还可以用切片一行完成展示你熟悉语言特性。5.3 面试答题节奏从暴力到最优的递进话术面试里遇到这道题不建议一上来就甩三次翻转。我的习惯节奏是这样的先复述题意确认k是否可能大于数组长度、是否允许额外空间。这一步体现出你注意边界条件。给出暴力解法说清楚它O(n*k)的问题。主动提出额外数组解法O(n)时间O(n)空间讲解下标映射(i k) % n。面试官追问能不能降低空间顺势讲三次翻转并把AB - reverse(B)reverse(A) - BA的推导写出来。如果面试官继续深挖再给出环状替换强调gcd决定的环数量和count计数器。这套递进既能让面试官看到你从朴素到优化的完整思维路径也能避免直接写结论导致背题的观感。这道题的难点其实不在于想出最优解而在于能不能在紧张的环境下一次写对边界条件。最后讲一点个人体会。轮转数组看起来只是Hot 100里一个不太起眼的Medium但它是极少数我能用同一道题讲清楚暴力优化、取模边界、原地修改、多方案对比四件事的题目。我后来每次面试前都会把它当作热身题不是为了刷熟练度而是为了让自己重新进入先想边界、再想复杂度、最后动手写的答题状态。如果你正在刷题这道题值得多写几遍——第一遍用额外数组保证正确第二遍用三次翻转压缩空间第三遍用环状替换检验自己对循环不变量的理解。三遍下来数组类题目的很多通用套路你基本就摸透了。