【Hot100|13-LeetCode 189. 轮转数组】
LeetCode 189. 轮转数组 - 三次反转原地算法详解
一、问题理解
问题描述
给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。要求原地修改数组，不使用额外的数组空间。
示例
text
输入: 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] 输入: nums = [-1,-100,3,99], k = 2 输出: [3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
要求
原地修改：不能使用额外的数组空间
时间复杂度：尽可能高效
空间复杂度：O(1)
二、核心思路：三次反转法
为什么需要三次反转？
问题本质：将数组后
k个元素移动到前面直观思路：可以先反转整个数组，这样后
k个元素就到了前面，但顺序反了调整顺序：再分别反转前
k个元素和后n-k个元素，恢复正确的顺序
三次反转步骤
反转整个数组：将整个数组反转，这样原数组的后
k个元素就变成了前k个元素反转前 k 个元素：恢复前
k个元素的原始顺序反转后 n-k 个元素：恢复后
n-k个元素的原始顺序
三、代码逐行解析
Java 解法
java
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; // 1. 处理 k 大于数组长度的情况 k = k % n; // 2. 反转整个数组 reverse(nums, 0, n - 1); // 3. 反转前 k 个元素 reverse(nums, 0, k - 1); // 4. 反转后 n-k 个元素 reverse(nums, k, n - 1); } // 辅助函数：反转数组中指定范围的元素 private void reverse(int[] nums, int start, int end) { while (start < end) { // 交换 start 和 end 位置的元素 int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; // 移动指针 start++; end--; } } }Python 解法
python
from typing import List class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ # 1. 定义反转函数 def reverse(i: int, j: int) -> None: """反转 nums 中从索引 i 到 j 的元素（闭区间）""" while i < j: # 交换元素 nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 n = len(nums) # 2. 处理 k 大于数组长度的情况 k %= n # 轮转 k 次等于轮转 k % n 次 # 3. 三次反转 reverse(0, n - 1) # 反转整个数组 reverse(0, k - 1) # 反转前 k 个元素 reverse(k, n - 1) # 反转后 n-k 个元素
四、Java 与 Python 语法对比
1. 数组/列表操作
| 操作 | Java | Python |
|---|---|---|
| 数组/列表长度 | nums.length | len(nums) |
| 交换元素 | 需要临时变量 | a, b = b, a |
| 取模运算 | k % n | k % n |
| 函数定义 | private void reverse(...) | def reverse(...) -> None: |
2. 循环与控制流
| 操作 | Java | Python |
|---|---|---|
| while 循环 | while (start < end) { ... } | while i < j: |
| 指针移动 | start++; end--; | i += 1; j -= 1 |
| 函数调用 | reverse(nums, 0, n-1) | reverse(0, n-1) |
3. 原地修改
| 操作 | Java | Python |
|---|---|---|
| 修改原数组 | 直接修改数组元素 | 直接修改列表元素 |
| 空间复杂度 | O(1) | O(1) |
五、实例演示
以nums = [1,2,3,4,5,6,7],k = 3为例，演示三次反转过程：
初始状态
text
原始数组: [1, 2, 3, 4, 5, 6, 7] n = 7, k = 3
步骤1：反转整个数组
text
反转整个数组 (0 到 6): [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
步骤2：反转前 k 个元素 (0 到 2)
text
反转前3个元素 (0 到 2): [7,6,5,4,3,2,1] -> [5,6,7,4,3,2,1]
步骤3：反转后 n-k 个元素 (3 到 6)
text
反转后4个元素 (3 到 6): [5,6,7,4,3,2,1] -> [5,6,7,1,2,3,4]
最终结果
text
[5,6,7,1,2,3,4]
可视化过程
text
原始: [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]
六、关键细节解析
1. 为什么要对k取模？
当
k > n时，旋转k次等价于旋转k % n次例如：数组长度 7，旋转 10 次等价于旋转 3 次
避免不必要的重复旋转
2. 为什么这种方法能工作？
数学证明：
设原数组为A，目标数组为B，其中B[i] = A[(i - k) % n]
三次反转的过程：
反转整个数组：
A[i] → A[n-1-i]反转前 k 个元素：前 k 个元素恢复原始顺序
反转后 n-k 个元素：后 n-k 个元素恢复原始顺序
直观理解：
将数组分为两部分：
[前 n-k 个元素]和[后 k 个元素]目标是：
[后 k 个元素] + [前 n-k 个元素]通过三次反转实现这个目标
3. 边界情况处理
k = 0：不需要旋转，直接返回
k = n：旋转 n 次等于不旋转（取模后为 0）
n = 1：只有一个元素，无论 k 是多少，数组不变
k > n：取模后处理
4. 为什么不能使用切片？
切片会创建新的数组/列表，违反原地修改的要求
空间复杂度变为 O(n)，不符合题目要求
七、复杂度分析
时间复杂度：O(n)
反转整个数组：O(n)
反转前 k 个元素：O(k)
反转后 n-k 个元素：O(n-k)
总时间复杂度：O(n) + O(k) + O(n-k) = O(n)
空间复杂度：O(1)
只使用了常数个额外变量
原地修改，没有使用额外数组空间
八、其他解法对比
1. 暴力法（逐个旋转）
python
def rotate_brute_force(nums, k): 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)，最坏情况下 O(n²)
空间复杂度：O(1)
2. 使用额外数组
python
def rotate_extra_array(nums, k): n = len(nums) k %= n # 创建新数组 rotated = [0] * n for i in range(n): # 计算新位置 new_index = (i + k) % n rotated[new_index] = nums[i] # 将结果复制回原数组 for i in range(n): nums[i] = rotated[i]
复杂度：
时间复杂度：O(n)
空间复杂度：O(n)，不符合原地修改要求
3. 环状替换法
python
def rotate_cyclic(nums, k): n = len(nums) k %= n # 计算需要处理的环的数量 count = 0 start = 0 while count < n: current = start prev = nums[start] while True: # 计算下一个位置 next_index = (current + k) % n # 保存下一个位置的元素 temp = nums[next_index] # 将前一个元素放到当前位置 nums[next_index] = prev # 更新变量 prev = temp current = next_index count += 1 # 如果回到起点，结束当前环 if start == current: break start += 1
复杂度：
时间复杂度：O(n)
空间复杂度：O(1)
缺点：逻辑复杂，容易出错
九、常见问题与解答
Q1: 如果 k 是负数怎么办？
A1: 题目说明 k 是非负数，所以不需要处理负数情况。但如果需要处理，可以将负数转换为正数：k = k % n + n
Q2: 为什么不能直接使用切片？
A2: 切片会创建新的列表，违反原地修改的要求。题目明确要求 "Do not return anything, modify nums in-place instead."
Q3: 这个算法适用于所有情况吗？
A3: 是的，算法适用于所有情况，包括：
空数组（n=0）：不会执行任何操作
单个元素（n=1）：不会改变
k=0：不会改变
k>=n：取模后处理
Q4: 这个算法容易理解吗？
A4: 三次反转算法需要一些思考才能理解，但一旦理解就很容易记忆。它是解决旋转数组问题的经典算法。
Q5: 有没有更直观的解法？
A5: 环状替换法更直观（直接按照旋转的数学定义移动元素），但实现更复杂。三次反转法实现简单且高效。
十、相关题目
1. LeetCode 61. 旋转链表
python
def rotateRight(head, k): if not head or not head.next or k == 0: return head # 计算链表长度 length = 1 tail = head while tail.next: tail = tail.next length += 1 # 处理 k k %= length if k == 0: return head # 找到新的尾节点 new_tail = head for _ in range(length - k - 1): new_tail = new_tail.next # 重新连接链表 new_head = new_tail.next new_tail.next = None tail.next = head return new_head
2. LeetCode 396. 旋转函数
python
def maxRotateFunction(nums): n = len(nums) total_sum = sum(nums) # 计算 F(0) f0 = 0 for i in range(n): f0 += i * nums[i] max_val = f0 current = f0 # 计算 F(1) 到 F(n-1) for k in range(1, n): # F(k) = F(k-1) + sum(nums) - n * nums[n-k] current = current + total_sum - n * nums[n - k] max_val = max(max_val, current) return max_val
3. LeetCode 151. 反转字符串中的单词
python
def reverseWords(s): # 移除多余空格 words = s.split() # 反转单词顺序 words.reverse() # 用空格连接单词 return ' '.join(words)
十一、总结
核心要点
三次反转是关键：通过三次反转实现数组的原地旋转
取模操作很重要：处理 k 大于数组长度的情况
原地修改要求：不能使用额外数组空间
算法步骤
计算
k = k % n，处理 k 大于数组长度的情况反转整个数组
反转前 k 个元素
反转后 n-k 个元素
时间复杂度与空间复杂度
时间复杂度：O(n)，每个元素被访问两次（反转时）
空间复杂度：O(1)，只使用常数个额外变量
适用场景
需要原地修改数组
需要高效旋转数组元素
不允许使用额外数组空间
扩展思考
这个算法展示了如何通过简单的操作（反转）实现复杂的变化（旋转）。类似的思想可以应用到其他问题中，如：
字符串旋转
链表旋转
矩阵旋转
掌握三次反转算法，不仅能够解决轮转数组问题，还能够理解原地操作和数组操作的核心技巧，是面试中非常重要的算法技能。