189. 轮转数组
题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
要求：使用 O(1) 额外空间（原地修改）。
示例
示例 1：
输入: 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]
示例 2：
输入: nums = [-1,-100,3,99], k = 2
输出: [3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
解题思路
第一步：理解问题本质
数组向右轮转 k 个位置，意味着：
- 最后 k 个元素会移动到数组前面
- 前面 n-k 个元素会移动到数组后面
例如 [1,2,3,4,5,6,7] 轮转 3 位后变成 [5,6,7,1,2,3,4]。
第二步：暴力解法
每次将数组最后一个元素取出，所有元素右移一位，再将取出的元素放到首位。重复 k 次。
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
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)，当 k 接近 n 时达到 O(n²)。
第三步：优化解法 - 使用额外数组
创建一个新数组，直接按轮转后的位置放置元素。
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
temp = nums[:] # 复制原数组
for i in range(n):
nums[(i + k) % n] = temp[i]
分析：时间复杂度 O(n)，但需要 O(n) 额外空间。
第四步：最优解法 - 三次翻转法
这是本题最优雅的解法，通过三次翻转实现原地轮转：
- 翻转整个数组
[0, n-1] - 翻转前 k 个元素
[0, k-1] - 翻转剩余元素
[k, n-1]
为什么这样有效？
假设原数组为 [1,2,3,4,5,6,7]，k=3：
| 步骤 | 操作 | 结果 | 说明 |
|---|---|---|---|
| 初始 | - | [1,2,3,4,5,6,7] | 原数组 |
| 第1步 | 整体翻转 | [7,6,5,4,3,2,1] | 顺序完全颠倒 |
| 第2步 | 翻转前3个 | [5,6,7,4,3,2,1] | 前3个恢复正确顺序 |
| 第3步 | 翻转后4个 | [5,6,7,1,2,3,4] | 后4个恢复正确顺序 |
数学原理：翻转操作具有对称性，三次特定的翻转组合恰好能产生轮转效果。
完整代码实现
from typing import List
class Solution:
"""
轮转数组 - 数组翻转法
核心思路：
通过三次翻转实现数组轮转：
1. 先翻转整个数组 [0, n-1]
2. 再翻转前 k 个元素 [0, k-1]
3. 最后翻转剩余元素 [k, n-1]
时间复杂度：O(n)
空间复杂度：O(1)
"""
def rotate(self, nums: List[int], k: int) -> None:
"""Do not return anything, modify nums in-place instead."""
n = len(nums)
k %= n # 处理 k > n 的情况
# 三次翻转实现轮转效果
self.reverse(nums, 0, n - 1) # 第一步：翻转整个数组
self.reverse(nums, 0, k - 1) # 第二步：翻转前 k 个元素
self.reverse(nums, k, n - 1) # 第三步：翻转剩余元素
def reverse(self, nums: List[int], left: int, right: int) -> None:
"""辅助函数：反转数组区间 [left, right]"""
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
示例推演
以 nums = [1,2,3,4,5,6,7], k = 3 为例：
第一步：k %= n
- k = 3 % 7 = 3
第二步：翻转整个数组 [0, 6]
- 初始:
[1,2,3,4,5,6,7] - 交换 1↔7:
[7,2,3,4,5,6,1] - 交换 2↔6:
[7,6,3,4,5,2,1] - 交换 3↔5:
[7,6,5,4,3,2,1] - 中间元素 4 无需交换
- 结果:
[7,6,5,4,3,2,1]
第三步：翻转前 k=3 个元素 [0, 2]
- 初始:
[7,6,5,4,3,2,1] - 交换 7↔5:
[5,6,7,4,3,2,1] - 结果:
[5,6,7,4,3,2,1]
第四步：翻转剩余元素 [3, 6]
- 初始:
[5,6,7,4,3,2,1] - 交换 4↔1:
[5,6,7,1,3,2,4] - 交换 3↔2:
[5,6,7,1,2,3,4] - 结果:
[5,6,7,1,2,3,4]✓
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力 | O(n×k) | O(1) | 每次移动一位，重复k次 |
| 优化 | O(n) | O(n) | 使用额外数组存储 |
| 最优（三次翻转） | O(n) | O(1) | 每个元素被访问常数次，原地操作 |
易错点总结
1. k 可能大于数组长度
错误：直接使用 k 作为翻转边界。
正确：k %= n，因为轮转 n 次等于原数组。
# 错误
k = k # 当 k > n 时会出错
# 正确
k %= n # 处理 k > n 的情况
2. 翻转边界处理
翻转区间 [left, right] 是闭区间，双指针相遇时停止。
while left < right: # 不是 <=
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
3. 三次翻转的顺序
必须是：整体 → 前k个 → 剩余。顺序错误会导致错误结果。
扩展思考
1. 向左轮转怎么办？
向左轮转 k 位等价于向右轮转 n-k 位：
def rotate_left(nums, k):
n = len(nums)
rotate_right(nums, n - k % n)
2. 相关题目
3. 算法本质
三次翻转法的本质是置换群的应用。数组轮转可以看作是一个循环置换，而翻转操作可以分解和重组这个置换。