LeetCode 189数组轮转问题详解：辅助数组法与三次翻转法
LeetCode 189数组轮转问题详解：辅助数组法与三次翻转法
前言
在数组相关面试题中，LeetCode 189《轮转数组》是一道非常经典的题目。
题目要求将数组中的元素整体向右移动 k 个位置，并且直接修改原数组。看似只是简单的数据移动，但实际上涉及索引映射、取模运算以及原地算法等知识点。
本文将详细介绍两种常见解法：
- 辅助数组法（容易理解）
- 三次翻转法（面试高频）
并分析两种方案的优缺点和适用场景。
一、题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置。
示例：
输入： nums=[1,2,3,4,5,6,7]k=3输出：[5,6,7,1,2,3,4]可以理解为：
原数组： 1 2 3 4 5 6 7 向右移动3位： 5 6 7 1 2 3 4方法一：辅助数组法
思路分析
对于数组中的每一个元素，都可以直接计算出它轮转后的新位置。
假设：
- 数组长度为 n
- 当前元素下标为 i
- 向右移动 k 位
则新的下标为：
(i+k)%n这里的%用于处理越界情况。
例如：
nums=[1,2,3,4,5]k=2| 原下标 | 新下标 |
|---|---|
| 0 | 2 |
| 1 | 3 |
| 2 | 4 |
| 3 | 0 |
| 4 | 1 |
最终结果：
[4,5,1,2,3]代码实现
fromtypingimportListclassSolution:defrotate(self,nums:List[int],k:int)->None:n=len(nums)k%=n new_nums=[0]*nforiinrange(n):new_nums[(i+k)%n]=nums[i]foriinrange(n):nums[i]=new_nums[i]图解过程
原数组： 1 2 3 4 5 6 7 0 1 2 3 4 5 6 k = 3元素移动：
1 → 下标3 2 → 下标4 3 → 下标5 4 → 下标6 5 → 下标0 6 → 下标1 7 → 下标2得到：
5 6 7 1 2 3 4复杂度分析
时间复杂度：
O(n)空间复杂度：
O(n)因为额外申请了一个与原数组等长的辅助数组。
优缺点
优点：
- 思路直观
- 最容易写对
- 适合刷题入门
缺点：
- 需要额外 O(n) 空间
方法二：三次翻转法
为什么想到翻转？
观察下面这个例子：
[1,2,3,4,5,6,7]向右移动3位：
[5,6,7,1,2,3,4]实际上可以看成：
前半部分： 1 2 3 4 后半部分： 5 6 7把后半部分移动到前面即可。
问题在于如何原地完成。
核心技巧
通过三次翻转实现。
第一次：翻转整个数组
1 2 3 4 5 6 7 ↓ 7 6 5 4 3 2 1第二次：翻转前 k 个元素
k = 3
7 6 5 | 4 3 2 1 ↓ 5 6 7 | 4 3 2 1第三次：翻转剩余元素
5 6 7 | 4 3 2 1 ↓ 5 6 7 | 1 2 3 4最终结果：
5 6 7 1 2 3 4成功完成轮转。
代码实现
fromtypingimportListclassSolution:defrotate(self,nums:List[int],k:int)->None:n=len(nums)k%=ndefreverse(left,right):whileleft<right:nums[left],nums[right]=nums[right],nums[left]left+=1right-=1reverse(0,n-1)reverse(0,k-1)reverse(k,n-1)复杂度分析
时间复杂度：
O(n)虽然执行了三次翻转，但每个元素仅被访问常数次。
空间复杂度：
O(1)只使用了有限个辅助变量。
为什么三次翻转一定正确？
第一次翻转后：
A B ↓ B反 A反其中：
A = 前 n-k 个元素 B = 后 k 个元素第二次翻转：
B反 → B第三次翻转：
A反 → A最终得到：
B A这正是向右轮转 k 位后的结果。
两种方案对比
| 方案 | 时间复杂度 | 空间复杂度 | 推荐程度 |
|---|---|---|---|
| 辅助数组法 | O(n) | O(n) | ★★★★★ |
| 三次翻转法 | O(n) | O(1) | ★★★★★ |
面试如何回答？
如果面试官问：
如何实现数组右旋 k 位？
建议按照下面顺序回答：
第一步：
先说最容易想到的辅助数组法。
利用 (i+k)%n 计算元素的新位置， 时间 O(n)，空间 O(n)。第二步：
进一步优化空间。
利用三次翻转： 整体翻转 → 翻转前k个 → 翻转后n-k个 时间 O(n) 空间 O(1)这样能体现你不仅会做题，还具备优化思维。
总结
轮转数组本质上是一个下标映射问题。
辅助数组法利用：
(i+k)%n直接计算元素的新位置，实现简单、容易理解。
三次翻转法则利用数组翻转的性质，在不申请额外空间的情况下完成轮转，是这道题最经典、最常考的解法。
刷题阶段建议先掌握辅助数组法，理解轮转规律；面试阶段重点掌握三次翻转法，这是面试官最希望看到的解法。
-删除浏览历史)
