【忍者算法】从风扇叶片到数组轮转：探索轮转数组问题｜LeetCode 189 轮转数组
从风扇叶片到数组轮转：探索轮转数组问题生活中的算法
想象你在看一个风扇缓缓转动，每次转动三个叶片的距离。原本在上方的叶片转到了右侧，原本在右侧的叶片转到了下方...这就是一个生动的轮转过程。再比如，幼儿园老师让小朋友们围成一个圈，喊"向右移动3个位置"，每个小朋友就会走到新的位置上。
这种轮转在生活中处处可见：餐厅的轮转座位安排、值班表的轮转、超市商品的轮换陈列，甚至是农田的轮作制度。它们都体现了同样的规律：保持原有顺序，整体移动特定步数。
问题描述
LeetCode第189题"轮转数组"是这样描述的：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
例如：
输入: nums = , k = 3输出: 解释:向右轮转 1 步: 向右轮转 2 步: 向右轮转 3 步: 最直观的解法：临时数组
就像小朋友们轮转位置时，先站到新位置再坐下。我们可以用一个临时数组记录每个元素的新位置。
让我们用一个简单的例子来理解：
原数组：, k = 21. 创建临时数组：2. 1应该移动到位置(0+2)%4=2：3. 2应该移动到位置(1+2)%4=3：4. 3应该移动到位置(2+2)%4=0：5. 4应该移动到位置(3+2)%4=1：6. 复制回原数组：优化解法：三次翻转
仔细观察会发现一个有趣的规律：如果我们把数组分成两部分，右边k个元素和左边其余元素，只需要三步就能完成轮转：
[*]翻转整个数组
[*]翻转前k个元素
[*]翻转后面的元素
就像打扑克牌时的切牌技巧：先整叠反转，再分别调整两叠的顺序。
三次翻转的原理
用餐桌座位来理解：
[*]所有人起立，从左到右交换位置（整体翻转）
[*]前k个人调整自己的相对位置（前k个翻转）
[*]剩下的人调整自己的相对位置（剩余部分翻转）
示例演示
用nums = , k = 2来说明：
原始数组：1. 整体翻转： -> 2. 翻转前k个： -> 3. 翻转剩余部分： -> Java代码实现
public void rotate(int[] nums, int k) { if (nums == null || nums.length <= 1) { return; } // 处理k大于数组长度的情况 k = k % nums.length; if (k == 0) return; // 1. 翻转整个数组 reverse(nums, 0, nums.length - 1); // 2. 翻转前k个元素 reverse(nums, 0, k - 1); // 3. 翻转剩余元素 reverse(nums, k, nums.length - 1);}private void reverse(int[] nums, int start, int end) { while (start < end) { // 交换首尾元素 int temp = nums; nums = nums; nums = temp; start++; end--; }}解法比较
让我们比较这两种方法：
临时数组法：
[*]时间复杂度：O(n)
[*]空间复杂度：O(n)
[*]优点：思路直观，易于理解
[*]缺点：需要额外空间
三次翻转法：
[*]时间复杂度：O(n)
[*]空间复杂度：O(1)
[*]优点：空间效率高，实现简单
[*]缺点：思路不够直观
思考启发
这道题告诉我们：
[*]有时候直观的解法不一定是最优的
[*]观察数据规律很重要
[*]在处理环形结构时，取余运算很有用
[*]翻转操作可以用来改变元素位置关系
类似的问题还有：
[*]反转字符串
[*]字符串轮转
[*]循环队列的实现
小结
通过轮转数组这道题，我们不仅学会了一个经典的数组操作技巧，更重要的是理解了如何通过观察数据特征，找到优雅的解决方案。记住，当遇到需要移动元素位置的问题时，考虑一下翻转操作是否能帮助我们！
<hr>作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
页:
[1]