给定一个整数数组 nums，将数组中的元素向右轮转 k个位置，其中 k是非负数。
示例 1:
输入: 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]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
我首先想到的是类似于剪下来，然后贴到后面去这样的算法，然后发现还可以通过翻转做。
解法一
1. 算法核心思想
采用辅助数组的策略实现数组轮转 。整体思路上，借助一个临时数组 temp 来完成元素位置的调度 。通过计算出轮转的切割分界点，先将尾部因轮转会移动到前方的元素放入临时数组，再将原数组头部的元素顺接至其后方，最终将临时数组的内容覆盖回原数组 。
2. 执行逻辑梳理
- 处理轮转周期： 数组轮转具有周期性。代码开头通过
if (k > nums.size())结合取模运算k % nums.size()，去除了超出数组长度的多余轮转次数 。这保证了后续的轮转步数处于合法范围内，避免了数组寻址越界 。 - 确定分界点： 创建辅助数组
temp后，计算出变量mid = nums.size() - k。该变量代表原数组在执行轮转时的绝对分界线 。 - 尾部元素前调： 第一个
for循环从分界线mid遍历至原数组末尾 。这一步将受轮转影响需要移动到数组前方的元素，按顺序写入temp数组的头部区域 。 - 头部元素后移： 第二个
for循环从原数组索引 0 遍历至mid。将原数组前半部分未发生越界的数据，顺延写入至temp数组已有数据的后方 。 - 最终数据回填： 此时
temp数组已完成所有元素的重新排列。最后一个for循环遍历将temp数组的所有数据重新赋值给原数组nums，以此完成原地修改的题目要求 。
class 轮转数组 {
public:
void rotate(vector<int>& nums, int k) {
if (k > nums.size()) {
k = k % nums.size();
}
vector<int> temp = vector<int>(nums.size(),0);
int mid = nums.size()-k;
int j = 0;
for (int i = mid; i < nums.size(); i++) {
temp[j] = nums[i];
j++;
}
for (int i = 0;i < mid;i++) {
temp[j] = nums[i];
j++;
}
for (int i = 0;i < nums.size(); i++) {
nums[i] = temp[i];
}
}
};
3. 复杂度分析
- 时间复杂度： O(n)。代码中虽然包含了三个
for循环，但它们属于并列关系，分别遍历了数组的不同区间 。整体相当于对数组进行了线性的遍历，时间效率符合要求 。 - 空间复杂度： O(n)。算法在函数内部申请了一个与原数组规模相同的
temp数组，因此额外消耗了随数组规模线性增长的内存空间 。
解法二
1. 算法核心思想
采用“三次反转”的策略实现数组的原地轮转。整体思路上，通过对数组的不同区间进行三次翻转动作，达到元素位置重新排列的目的 。这种写法不需要开辟额外的辅助数组，能够在空间复杂度为 O(1) 的情况下完成数组轮转 。
2. 执行逻辑梳理
- 处理轮转周期： 数组轮转具有周期性。代码开头通过
if (k > nums.size())结合取模运算k % nums.size()，去除了超出数组长度的多余轮转次数 。这保证了后续的轮转步数处于合法范围内，避免了数组寻址越界。 - 整体反转： 第一次调用
reverse将整个数组头尾对调 。此时，原本位于尾部需要轮转到前方的元素被移动到了数组的前部，但其内部顺序是倒序的；原本位于头部的元素被移动到了后部，内部顺序也是倒序的。 - 前部反转： 第二次调用
reverse将数组前k个元素再次反转 。这一步将前部元素的内部顺序恢复为原数组中的相对顺序 。 - 尾部反转： 第三次调用
reverse将数组后面剩余的元素反转回来 。这一步将后部元素的内部顺序恢复正常，至此完成整个数组的轮转 。
class 轮转数组 {
//翻面做法
public:
void rotate(vector<int>& nums, int k) {
if (k > nums.size()) {
k = k % nums.size();
}
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
3. 复杂度分析
- 时间复杂度： O(n)。算法共执行了三次反转操作，总体相当于对数组进行线性的遍历，时间效率符合要求。
- 空间复杂度： O(1)。该解法全程直接在原数组上进行元素修改，没有任何额外的内存开销，实现了原地修改 。