LeetCode-Go 189. Rotate Array：原地 O(1) 空间的数组旋转实现与三次翻转法详解

LeetCode-Go 189. Rotate Array原地 O(1) 空间的数组旋转实现与三次翻转法详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 LeetCode-Go 仓库中 189. Rotate Array 题解为核心完整覆盖题目要求、两种官方题解额外数组法与三次翻转原地法的 Go 实现并结合 测试文件 与仓库的 覆盖率测试脚本 说明如何验证解法。读完本篇你可以掌握数组旋转问题的最终态分析、k % n归约技巧、原地翻转的边界处理以及该仓库「每题独立目录 表驱动测试」的工程组织方式。题目与输入输出题目要求给定一个数组将数组中的元素向右移动k个位置其中k是非负数。Follow up:尽可能想出多种解法至少有 3 种不同的方式。能否做到原地in-place且只使用 O(1) 额外空间仓库文档给出了两个标准示例见 leetcode/0189.Rotate-Array/README.md示例 1Input: nums [1,2,3,4,5,6,7], k 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]示例 2Input: nums [-1,-100,3,99], k 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]约束条件Constraints1 nums.length 2 * 10^4-2^31 nums[i] 2^31 - 10 k 10^5注意k的上限10^5远大于nums.length的上限2 * 10^4这决定了任何正确解法都必须先对k做归约否则逐位移动 k 次的模拟实现必然超时。解法二额外数组法O(n) 空间原文档给出的解法二使用一个额外的数组先将原数组下标为i的元素移动到(ik) mod n的位置再将结果拷贝回原数组。对应 189. Rotate Array.go 中的实现// 解法二 时间复杂度 O(n)空间复杂度 O(n) func rotate1(nums []int, k int) { newNums : make([]int, len(nums)) for i, v : range nums { newNums[(ik)%len(nums)] v } copy(nums, newNums) }实现要点核心映射是newNums[(ik)%len(nums)] v下标i的元素右移k位后落到(ik) mod n取模天然处理了「越过数组尾部绕回头部」的情况k本身不必先取模因为(ik) mod n中的取模运算已经把k的整数倍部分吸收了最后用标准库copy(nums, newNums)把结果整体拷回保证满足「原地修改入参数组」的 LeetCode 约定即修改通过切片底层的同一块内存反映到调用方。该解法时间复杂度 O(n)、空间复杂度 O(n)胜在直观但它不满足 Follow up 中「in-place with O(1) extra space」的要求因此不是本题的最优解。解法一三次翻转法O(1) 空间最优解原文档的解题思路是由于题目要求不能使用额外空间本题最佳解法是解法一——先确定最终态再通过三次翻转变换得到。最终态分析数组向右旋转k位后末尾k mod n个元素移动到了数组头部剩下的元素右移k mod n个位置到最尾部。以示例 1n7, k3为例原数组: [1,2,3,4,5,6,7] 旋转后: [5,6,7 | 1,2,3,4] └头部┘ └──尾部──┘ 末尾 k 个元素 其余元素整体右移变换过程原文档描述的三步先将整个数组从头到尾翻转一次末尾的所有元素都到了头部再将[0, (k mod n) − 1]区间内的元素翻转一次最后将[k mod n, n − 1]区间内的元素翻转一次。对应源码实现// 解法一 时间复杂度 O(n)空间复杂度 O(1) func rotate(nums []int, k int) { k % len(nums) reverse(nums) reverse(nums[:k]) reverse(nums[k:]) } func reverse(a []int) { for i, n : 0, len(a); i n/2; i { a[i], a[n-1-i] a[n-1-i], a[i] } }用示例 1 走一遍验证三步翻转的正确性初始: [1, 2, 3, 4, 5, 6, 7] (k 3 % 7 3) 整段翻转后: [7, 6, 5, 4, 3, 2, 1] 翻转前 k 段: [5, 6, 7, 4, 3, 2, 1] 翻转后段: [5, 6, 7, 1, 2, 3, 4] ✓ 与期望输出一致实现细节解读k % len(nums)把k归约到[0, n-1]。约束中k最大可到10^5而n最大2*10^4这一步既避免无意义的完整轮换k % n 0时直接原地不动也保证后续切片nums[:k]、nums[k:]合法reverse是经典的双指针原地交换for i, n : 0, len(a); i n/2; i只走一半长度a[i], a[n-1-i] a[n-1-i], a[i]利用 Go 的多值赋值语法无需临时变量完成交换。整个翻转只读写了切片头指针和长度不分配新数组这就是空间复杂度 O(1) 的来源严格来说是 O(1) 个栈变量切片nums[:k]与nums[k:]与原数组共享底层内存对其原地修改等价于修改原数组对应区间这正是 Go 切片语义带来的便利——无需传递额外索引参数即可表达「区间翻转」。复杂度汇总解法时间复杂度空间复杂度是否原地解法一三次翻转O(n)O(1)是解法二额外数组O(n)O(n)否原文档还提到「至少有 3 种不同的解法」第三种经典思路是循环置换法按gcd(n, k)条循环链逐个位置放置元素同样可以做到 O(1) 空间本仓库题解以三次翻转作为最优解给出。测试用例与运行方式仓库为本题配置了表驱动测试 189. Rotate Array_test.go结构与文档中的两个示例一一对应type para189 struct { nums []int k int } type ans189 struct { one []int } func Test_Problem189(t *testing.T) { qs : []question189{ { para189{[]int{1, 2, 3, 4, 5, 6, 7}, 3}, ans189{[]int{5, 6, 7, 1, 2, 3, 4}}, }, { para189{[]int{-1, -100, 3, 99}, 2}, ans189{[]int{3, 99, -1, -100}}, }, } // ... 对每组输入先后调用 rotate 与 rotate1 并打印结果 }从测试代码结构看同一组输入会先后经过rotate(p.nums, p.k)解法一和rotate1(p.nums, p.k)解法二两种实现便于对比两种解法在相同数据上的行为是否一致。运行验证的方式与仓库 gotest.sh 的 CI 做法一致# 全量运行所有题解测试并生成覆盖率文件 bash gotest.sh # 或单独运行本题 go test ./leetcode/0189.Rotate-Array/ -v该仓库整体追求 100% 测试覆盖率go.mod 声明模块为github.com/halfrost/LeetCode-Go要求 Go 1.19 及以上环境每题独立目录leetcode/NNNN.Title/含题解.go、_test.go与README.md三件套的组织方式让单题测试可以按包粒度独立执行。同模式问题延伸「右移 k 位 k 对长度取模归约」是本题的核心套路在同仓库的另一道旋转题 61. Rotate List 中可以看到数组版到链表版的迁移rotateRight函数同样先遍历求长度再判断(k % len) 0时直接返回、否则尾接成环后在len - k%len处断开。两题对照阅读有助于把「k 归约 环形视角」这一通用策略从数组推广到链表场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考