从风扇叶片到数组轮转：探索轮转数组问题

生活中的算法

想象你在看一个风扇缓缓转动，每次转动三个叶片的距离。原本在上方的叶片转到了右侧，原本在右侧的叶片转到了下方...这就是一个生动的轮转过程。再比如，幼儿园老师让小朋友们围成一个圈，喊"向右移动3个位置"，每个小朋友就会走到新的位置上.

这种轮转在生活中处处可见：餐厅的轮转座位安排、值班表的轮转、超市商品的轮换陈列，甚至是农田的轮作制度。它们都体现了同样的规律：保持原有顺序，整体移动特定步数.

Mô tả vấn đề

LeetCode第189题"轮转数组"是这样描述的：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数.

Ví dụ:

输入: 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]

最直观的解法：临时数组

就像小朋友们轮转位置时，先站到新位置再坐下。我们可以用一个临时数组记录每个元素的新位置.

让我们用一个简单的例子来理解:

原数组：[1,2,3,4], k = 2 1. 创建临时数组：[0,0,0,0] 2. 1应该移动到位置(0+2)%4=2：[0,0,1,0] 3. 2应该移动到位置(1+2)%4=3：[0,0,1,2] 4. 3应该移动到位置(2+2)%4=0：[3,0,1,2] 5. 4应该移动到位置(3+2)%4=1：[3,4,1,2] 6. 复制回原数组：[3,4,1,2]

优化解法：三次翻转

仔细观察会发现一个有趣的规律：如果我们把数组分成两部分，右边k个元素和左边其余元素，只需要三步就能完成轮转:

1. 翻转整个数组
2. 翻转前k个元素
3. 翻转后面的元素

就像打扑克牌时的切牌技巧：先整叠反转，再分别调整两叠的顺序.

三次翻转的原理

用餐桌座位来理解:

1. 所有人起立，从左到右交换位置（整体翻转）
2. 前k个人调整自己的相对位置（前k个翻转）
3. 剩下的人调整自己的相对位置（剩余部分翻转）

示例演示

用nums = [1,2,3,4,5], k = 2来说明:

原始数组：[1,2,3,4,5] 1. 整体翻转： [1,2,3,4,5] -> [5,4,3,2,1] 2. 翻转前k个： [5,4,3,2,1] -> [4,5,3,2,1] 3. 翻转剩余部分： [4,5,3,2,1] -> [4,5,1,2,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[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } }

解法比较

让我们比较这两种方法:

临时数组法:

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 优点：思路直观，易于理解
• 缺点：需要额外空间

三次翻转法:

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 优点：空间效率高，实现简单
• 缺点：思路不够直观

思考启发

这道题告诉我们:

1. 有时候直观的解法不一定是最优的
2. 观察数据规律很重要
3. 在处理环形结构时，取余运算很有用
4. 翻转操作可以用来改变元素位置关系

类似的问题还有:

• 反转字符串
• 字符串轮转
• 循环队列的实现

bản tóm tắt

通过轮转数组这道题，我们不仅学会了一个经典的数组操作技巧，更重要的是理解了如何通过观察数据特征，找到优雅的解决方案。记住，当遇到需要移动元素位置的问题时，考虑一下翻转操作是否能帮助我们！ 。

---

作者：忍者算法 公众号：忍者算法 。

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～ 。

最后此篇关于【忍者算法】从风扇叶片到数组轮转：探索轮转数组问题｜LeetCode189轮转数组的文章就讲到这里了,如果你想了解更多关于【忍者算法】从风扇叶片到数组轮转：探索轮转数组问题｜LeetCode189轮转数组的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。