LeetCode 189. 轮转数组：从直观模拟到最优原地算法

1. 题目描述(题目链接)：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例：

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]

2. 方法一：辅助数组法

核心思想是：开辟一个新的数组，将原数组中的每个元素直接放到它最终应该在的位置上。

核心公式推导：

对于原数组下标为 i 的元素，向右轮转 k 位后，它的新下标 new_index 为：new_index = (i + k) % n （其中 n 为数组长度）

class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); vector<int> nums2(n); // 将每个元素直接放到最终位置 for (int i = 0; i < n; i++) { nums2[(i + k) % n] = nums[i]; } // 将新数组拷贝回原数组 nums = nums2; } };

复杂度分析：

时间复杂度： O(N)，遍历一次数组。

空间复杂度： O(N)，需要创建一个与原数组等大的新数组。

3. 方法二：三次翻转法（最优解）

这是本题在面试中最受青睐的解法。

核心思路：

向右轮转 k 位，本质上就是将数组的后 k 个元素移动到前面。我们可以通过以下三步实现：

1. 整体翻转：将整个数组翻转。此时，原本在末尾的 k 个元素跑到了数组的最前面
2. 翻转前 k 个元素：将这 k 个元素恢复顺序。
3. 翻转剩余的 n-k 个元素：将剩余元素恢复顺序。

演示：

假设 nums = [1,2,3,4,5,6,7], k = 3

1. 整体翻转 [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
2. 翻转前 k 个 (前3个) [7,6,5] -> [5,6,7]。数组变为：[5,6,7,4,3,2,1]
3. 翻转剩余部分 (后4个) [4,3,2,1] -> [1,2,3,4]。数组变为：[5,6,7,1,2,3,4] (完成)

注意： 如果 k 大于数组长度，需要先进行 k = k % n 取余操作，因为轮转 n 次等于没轮转。

代码实现 (C++)：

class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); k = k % n; // 处理 k > n 的情况 // 使用 C++ STL 的 reverse 函数 reverse(nums.begin(), nums.end()); // 1. 整体翻转 reverse(nums.begin(), nums.begin() + k); // 2. 翻转前 k 个 reverse(nums.begin() + k, nums.end()); // 3. 翻转剩余部分 } };

复杂度分析：

时间复杂度：ON，每个元素被翻转了两次。

空间复杂度：O1，原地修改，不需要额外空间。

4. 方法三：环形替换法（原地算法）

这也是一种O(1)空间的原地算法，但逻辑比三次翻转法更复杂。

核心思路：

我们可以直接把每个元素放到它最终的位置上。如果我们从下标 0 开始，将 nums[0] 移动到 (0+k)%n，然后继续移动被覆盖的元素，我们会形成一个闭环。

但是，如果 n 和 k 的最大公约数大于 1，我们会在回到起点时，还有元素没有移动。因此，我们需要从下一个下标开始，继续这个过程，直到所有元素都被移动。

代码实现：

class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); k = k % n; int count = 0; // 记录已移动的元素个数 // 当已移动元素数小于 n 时继续 for (int start = 0; count < n; start++) { int current = start; int prev = nums[start]; do { // 计算下一个位置 int next = (current + k) % n; // 暂存下一个位置的值，并将 prev 放入 swap(nums[next], prev); // 移动到下一个位置 current = next; count++; } while (start != current); // 形成闭环后退出 } } };

复杂度分析：

时间复杂度： O(N)，每个元素只被访问和移动一次。

空间复杂度： O(1)。

5. 总结