网硕互联帮助中心189. 轮转数组
文章目录
- [189. 轮转数组](https://leetcode.cn/problems/rotate-array/)
-
- 思路一：辅助数组（空间换时间）
- 思路二：暴力循环（逐步移动）
- 思路三：三次反转（最优解）
- 三种解法对比总结
- 知识点拓展
- 结语
题目描述
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
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] 示例 2:
text 输入: nums = [-1,-100,3,99], k = 2 输出: [3,99,-1,-100]
解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100] 提示:
1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 – 1
0 <= k <= 10^5
思路一：辅助数组（空间换时间）
核心思想
这是最直观的思路：复制一份原数组作为"模板"，然后计算每个元素应该移动到哪个新位置，直接填入。你可以想象成：把原数组的元素看成"萝卜"，把数组位置看成"萝卜坑"。先把所有萝卜拿出来（复制到 temp），然后根据规则把萝卜一个个放回坑里。
位置计算公式
对于索引 i 的元素，它应该移动到 (i + k) % n 的位置。
为什么？向右轮转 k 步，就是每个元素往后移动 k 个位置。但数组是环形的，所以当 i + k 超过数组末尾时，需要回到开头。取模运算 % n 正好实现这个"循环"效果。
举例：[1,2,3,4,5,6,7], k = 3
索引 0 的元素 1 → (0+3)%7 = 3 → 新位置是索引 3
索引 4 的元素 5 → (4+3)%7 = 0 → 新位置是索引 0
代码实现
func rotate(nums []int, k int) {
n := len(nums)
k %= n // 处理 k > n 的情况，因为轮转 n 次等于没轮转
temp := make([]int, n)
copy(temp, nums) // temp 是原数组的副本
for i := 0; i < n; i++ {
newIndex := (i + k) % n
nums[newIndex] = temp[i]
}
}
复杂度分析
时间复杂度: O(n) — 遍历一次数组
空间复杂度: O(n) — 需要一个大小为 n 的辅助数组
优缺点
优点：思路简单，容易理解，不容易出错
缺点：需要额外 O(n) 空间，当 n 很大时可能受限
思路二：暴力循环（逐步移动）
核心思想
模拟轮转的过程：每次把数组所有元素向右移动一步，重复 k 次。就像排队时，每次队伍最后一个人走到最前面，其他人依次向后挪一个位置。
代码实现
go
func rotate(nums []int, k int) {
n := len(nums)
k %= n
for i := 0; i < k; i++ {
last := nums[n-1] // 保存最后一个元素
for j := n – 1; j > 0; j– {
nums[j] = nums[j-1] // 所有元素后移一位
}
nums[0] = last // 把最后一个放到最前面
}
}
复杂度分析
时间复杂度: O(k * n) — 每次轮转需要移动 n 个元素，共 k 次
空间复杂度: O(1) — 只用了常数额外空间
优缺点
优点：原地操作，不需要额外空间
缺点：当 k 很大时，效率极低。最坏情况 k = n，需要 O(n²) 时间
思路三：三次反转（最优解）
核心思想
这是本题最巧妙的解法。它的思路源于一个观察：向右轮转 k 位，本质上就是把数组分成两部分：前 n-k 个元素（前半段）和后 k 个元素（后半段），然后交换这两段的位置，把后半段放到前面，前半段放到后面。
问题转化成：如何用 O(1) 空间高效地交换数组的两段数据？答案是：利用"反转"操作。
反转操作有一个重要性质：对一个数组（或子数组）连续反转两次，它会恢复原样。基于这个性质，可以设计一个三步走的方案。
三步图解
以 nums = [1,2,3,4,5,6,7], k = 3 为例：
原始数组: [1 2 3 4 5 6 7]
|___前半段___| |_后半段_|
n-k=4 k=3
第1步: 反转整个数组
[1 2 3 4 5 6 7] → [7 6 5 4 3 2 1]
现在，后半段 [5,6,7] 跑到了最前面，但顺序是反的（[7,6,5]）
第2步: 反转前 k 个元素
[7 6 5 4 3 2 1] → 反转前3个 → [5 6 7 4 3 2 1]
现在，原后半段的顺序正过来了：[5,6,7]
第3步: 反转后 n-k 个元素
[5 6 7 4 3 2 1] → 反转后4个 → [5 6 7 1 2 3 4]
现在，原前半段的顺序也正过来了：[1,2,3,4]
最终结果: [5 6 7 1 2 3 4] ✅
为什么这能行？可以这样理解：反转三次 = “负负得正”。整体反转把两段数据的位置交换了，但每段内部的顺序都反了；局部反转分别把每段再反转一次，恢复它们内部的正确顺序。就像你把一副牌分成两摞，先把整副牌倒过来，再把每摞分别正过来。
代码实现
go
func reverse(arr []int) {
l, r := 0, len(arr)-1
for l <= r {
arr[l], arr[r] = arr[r], arr[l]
l++
r–
}
}
func rotate(nums []int, k int) {
n := len(nums)
k %= n
reverse(nums) // 反转整个数组
reverse(nums[:k]) // 反转前 k 个
reverse(nums[k:]) // 反转后 n-k 个
}
复杂度分析
时间复杂度: O(n) — 每个元素被交换常数次，精确为 n 次交换
空间复杂度: O(1) — 原地操作，没有额外空间
优缺点
优点：时间复杂度最优 O(n)，空间复杂度最优 O(1)，代码简洁优雅
缺点：思路比较巧妙，需要理解反转的"负负得正"效应
三种解法对比总结
解法 时间复杂度 空间复杂度 核心操作 适用场景 辅助数组 O(n) O(n) 直接计算新位置 思路最直观，面试首选 暴力循环 O(k*n) O(1) 逐步移动 不推荐，效率太低 三次反转 O(n) O(1) 反转操作 最优解，展示算法功底
知识点拓展
为什么需要 k %= n？如果 k 大于 n，轮转 k 次和轮转 k % n 次的效果是一样的。例如数组长度 n=7，轮转 10 次 = 轮转 3 次（因为 10 % 7 = 3）。
如果题目改为"向左轮转"怎么办？向左轮转 k 位，等同于向右轮转 n – k 位。所以代码只需要改成：rotate(nums, n – k % n)。
反转操作的边界条件：for l <= r，用 <= 确保中间元素也被处理（虽然交换自己不影响结果）。当数组长度为奇数时，中间元素会 l == r，交换自己，不影响结果。
结语
这道题是数组操作和原地算法的经典例题。从暴力解到最优解，展示了算法优化的思考路径：先想最直接的方法（辅助数组）→ 容易实现，但可能不够好；优化空间（暴力循环）→ 空间优化了，但时间变差；寻找更优的算法（三次反转）→ 时间和空间同时达到最优。
面试中，建议从辅助数组解法开始讲，然后逐步优化到三次反转，这样能展示你的思考过程和算法功底。
如果觉得这篇文章有帮助，欢迎点赞、收藏、关注！后续会持续分享更多算法题解和 Go 语言实战干货。我们下期见！👋
评论前必须登录！
注册