🔥个人主页：Milestone-里程碑
❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>
<<Git>><<MySQL>>
🌟心向往之行必能至
题目描述
给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。
示例 1输入：nums = [1,2,3,4,5,6,7],k = 3输出：[5,6,7,1,2,3,4]解释：向右轮转 3 步后，数组末尾的 3 个元素移动到了数组开头。
示例 2输入：nums = [-1,-100,3,99],k = 2输出：[3,99,-1,-100]
解法一：使用额外数组（直观易懂）
这是最容易想到的方法，通过一个临时数组来存储轮转后的结果，再拷贝回原数组。
思路
- 计算有效轮转步数
x = k % nums.size()，避免 k 大于数组长度时的无效轮转。 - 创建临时数组
temp，将原数组的后x个元素和前n-x个元素依次放入。 - 将临时数组的内容拷贝回原数组。
代码
cpp
void rotate(vector<int>& nums, int k) { int n = nums.size(); int x = k % n; vector<int> temp(n); for (int i = 0; i < n; ++i) { temp[(i + x) % n] = nums[i]; } nums = temp; }复杂度分析
- 时间复杂度：\(O(n)\)，遍历一次数组。
- 空间复杂度：\(O(n)\)，需要额外的临时数组存储结果。
解法二：三次反转（原地算法，最优解）
这是这道题的最优解法，不需要额外空间，仅通过三次反转操作就可以完成轮转。
思路
- 计算有效步数：
x = k % nums.size()，处理 k 大于数组长度的情况。 - 第一次反转：将整个数组反转。
- 第二次反转：将数组的前
x个元素反转。 - 第三次反转：将数组的剩余
n-x个元素反转。
示例演示（以nums = [1,2,3,4,5,6,7],k=3为例）
- 原数组：
[1,2,3,4,5,6,7] - 整体反转：
[7,6,5,4,3,2,1] - 反转前 3 个：
[5,6,7,4,3,2,1] - 反转后 4 个：
[5,6,7,1,2,3,4]
代码
cpp
#include <vector> #include <algorithm> using namespace std; class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); int x = k % n; if (x == 0) return; // 1. 反转整个数组 reverse(nums.begin(), nums.end()); // 2. 反转前x个元素 reverse(nums.begin(), nums.begin() + x); // 3. 反转剩余元素 reverse(nums.begin() + x, nums.end()); } };复杂度分析
- 时间复杂度：\(O(n)\)，三次反转操作的总时间为 \(O(n)\)。
- 空间复杂度：\(O(1)\)，仅使用常量级的额外空间。
解法三：环状替换（原地算法，进阶思路）
这是另一种原地算法，通过计算每个元素的目标位置，以环状的方式进行元素替换。
思路
- 计算有效步数
x = k % nums.size()。 - 从起始位置开始，将当前元素放到它轮转后的目标位置，再将目标位置的元素放到它的目标位置，直到回到起始位置。
- 如果一轮替换没有覆盖所有元素，则从下一个位置开始重复上述过程。
复杂度分析
- 时间复杂度：\(O(n)\)，每个元素只被移动一次。
- 空间复杂度：\(O(1)\)，仅使用常量级的额外空间。
三种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 额外数组 | \(O(n)\) | \(O(n)\) | 思路简单，容易实现，但需要额外空间 |
| 三次反转 | \(O(n)\) | \(O(1)\) | 最优解，原地操作，代码简洁高效 |
| 环状替换 | \(O(n)\) | \(O(1)\) | 原地操作，但逻辑 |
