普通数组----轮转数组

🔥个人主页：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]

解法一：使用额外数组（直观易懂）

这是最容易想到的方法，通过一个临时数组来存储轮转后的结果，再拷贝回原数组。

思路

1. 计算有效轮转步数x = k % nums.size()，避免 k 大于数组长度时的无效轮转。
2. 创建临时数组temp，将原数组的后x个元素和前n-x个元素依次放入。
3. 将临时数组的内容拷贝回原数组。

代码

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)\)，需要额外的临时数组存储结果。

解法二：三次反转（原地算法，最优解）

这是这道题的最优解法，不需要额外空间，仅通过三次反转操作就可以完成轮转。

思路

1. 计算有效步数：x = k % nums.size()，处理 k 大于数组长度的情况。
2. 第一次反转：将整个数组反转。
3. 第二次反转：将数组的前x个元素反转。
4. 第三次反转：将数组的剩余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)\)，仅使用常量级的额外空间。

解法三：环状替换（原地算法，进阶思路）

这是另一种原地算法，通过计算每个元素的目标位置，以环状的方式进行元素替换。

思路

1. 计算有效步数x = k % nums.size()。
2. 从起始位置开始，将当前元素放到它轮转后的目标位置，再将目标位置的元素放到它的目标位置，直到回到起始位置。
3. 如果一轮替换没有覆盖所有元素，则从下一个位置开始重复上述过程。

复杂度分析

• 时间复杂度：\(O(n)\)，每个元素只被移动一次。
• 空间复杂度：\(O(1)\)，仅使用常量级的额外空间。

三种解法对比