189. 轮转数组 (Medium)
专题归类： 数组 LeetCode 链接： https://leetcode.cn/problems/rotate-array/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，要求原地操作（即不使用额外数组）。
示例 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 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^5- 原地操作，空间复杂度 O(1)
题目详细分析
数据范围分析：
- 数组长度最大 10^5，O(n) 时间可行，O(n^2) 模拟会超时。
- k 的范围 0~10^5，可能大于 n，需要先取模
k %= n。 - 元素值范围是 32 位有符号整数，但操作不涉及计算，只是移动位置。
输入输出特征：
- 输入是整数数组和整数 k，输出（实际上是修改原数组）无返回值，但题目要求原地修改。
- 向右轮转 k 位：每个元素向右移动 k 步，末尾元素循环到开头。
边界条件：
- k = 0 → 数组不变。
- k 是 n 的倍数 → 数组不变（取模后为 0）。
- n = 1 → 轮转后不变（无论 k 是多少）。
- k > n → 实际效果等价于 k % n。
隐藏条件：
- “原地”意味着不能创建新数组然后复制回去。但可以使用 O(1) 额外空间。
- 三次翻转法是仅有的几种 O(1) 空间解法之一，面试中最常考察。
小白版直白理解
想象你有一排 7 张椅子，上面坐了 7 个人。老师说：“大家往右移动 3 个位置！”
但是最右边的人没位置了怎么办？坐好的同学回到左边空位继续坐。
这就叫轮转——像旋转木马一样转圈。
手工操作的笨办法： 每次让所有人往右挪一步，做 3 次。但人太多时可以更聪明：
聪明法（三次翻转法）： 就像你翻书一样——
- 把整本书倒过来（整体翻转）
- 把前 3 页正过来（前 k 个翻转）
- 把剩下的页正过来（后 n-k 个翻转）
神奇的事情发生了：所有内容就像轮转了一样！
解题思路
思路一：三次翻转法（推荐）
核心洞察：
向右轮转 k 位，相当于把数组后面的 k 个元素移到前面来。翻转操作可以帮助我们实现这个效果：
原始数组： [1, 2, 3, 4, 5, 6, 7] k=3
整体翻转： [7, 6, 5, 4, 3, 2, 1] ← 后面的到了前面
翻转前 k 个： [5, 6, 7, 4, 3, 2, 1] ← 恢复前 k 个的顺序
翻转后 n-k 个： [5, 6, 7, 1, 2, 3, 4] ← 恢复后 n-k 个的顺序
为什么这样可行？ 整体翻转让原数组的后 k 个元素到了前面（但顺序是反的），然后再对两部分分别翻转恢复顺序。
def rotate(nums, k):
n = len(nums)
k %= n # 处理 k > n 的情况
if k == 0:
return
# 辅助函数：翻转数组中 [l, r] 范围内的元素
def reverse(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
# 三次翻转
reverse(0, n - 1) # 1. 整体翻转
reverse(0, k - 1) # 2. 翻转前 k 个
reverse(k, n - 1) # 3. 翻转后 n-k 个复杂度： O(n) 时间，O(1) 空间。
思路二：环状替换（原地算法）
每个元素向右移动 k 步，相当于在环上移动。用一个变量 cur 记录当前位置，将 nums[cur] 放到 nums[(cur + k) % n] 的位置，被覆盖的值继续往下替换。
需要用一个计数器 count 确保所有元素都被移动过（每移动一个元素 count++），当 count == n 时结束。
注意：如果 n 和 k 不互质，会出现多个环。比如 n=6, k=4，gcd(6,4)=2，有 2 个环。
def rotate_cycle(nums, k):
n = len(nums)
k %= n
count = 0 # 已移动的元素个数
for start in range(n):
if count >= n:
break
cur = start
prev = nums[cur]
while True:
nxt = (cur + k) % n
nums[nxt], prev = prev, nums[nxt]
cur = nxt
count += 1
if cur == start: # 回到起点，一个环完成
break思路三：使用额外数组（不符合题意但最直观）
新建一个数组，将每个元素放到新位置，再复制回来。不符合 O(1) 空间要求，但最容易理解。
def rotate_copy(nums, k):
n = len(nums)
k %= n
result = [0] * n
for i in range(n):
result[(i + k) % n] = nums[i]
# 复制回原数组
for i in range(n):
nums[i] = result[i]易错点
- 忘记取模：
k %= n是最常见的遗漏步骤。当 k > n 时，直接使用 k 会导致数组越界或错误的移动。 - 三次翻转的顺序：必须是「整体 → 前 k 个 → 后 n-k 个」这个顺序。反了或者顺序错了结果会不同。
- k = 0 的情况：取模后 k=0，不需要任何操作，直接返回。
- n = 1 的情况：无论 k 是多少，轮转后不变。
- 环状替换的起始位置：如果 n 和 k 不互质，需要从多个起点开始循环，否则会漏掉元素。
- 原地要求：不能直接
nums = rotated_list这样赋值，这不会修改原数组（Python 中只是局部变量重绑定）。要修改原数组内容必须用索引赋值。
框架提炼
三次翻转法通用模板：
def rotate_array(nums, k):
n = len(nums)
if n == 0:
return
k %= n # Step 1: 处理 k > n
if k == 0:
return
# Step 2: 定义翻转函数
def reverse(arr, l, r):
while l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
# Step 3: 三次翻转
reverse(nums, 0, n - 1) # 整体翻转
reverse(nums, 0, k - 1) # 翻转前 k 个
reverse(nums, k, n - 1) # 翻转后 n-k 个这个模板适用的场景：
- 数组轮转（向右/向左）
- 字符串轮转
- 链表轮转（61-旋转链表）
核心原理： 翻转操作可以看作是「反转顺序」，通过三次不同范围的反转组合，可以实现元素的循环移动。
关联题目
- 61-旋转链表 — 链表版本的”轮转”，思路类似但操作方式是断链重接而非翻转，需要先找到第 n-k 个节点。
- 151-反转字符串中的单词 — 也使用了类似的翻转技巧：先翻转整个字符串，再逐个翻转单词。
- 48-旋转图像 — 矩阵旋转（二维的”轮转”），用到的是转置+翻转的组合，与一维数组的三次翻转有异曲同工之妙。
- 238-除自身以外数组的乘积 — 也是数组的原地操作题目，使用两遍遍历代替额外的存储空间。