旋转数组
题目描述
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [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:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。
思路1
每次向后移动一位，循环移动K次，即可达到将数组中的元素向右移动 k 个位置的效果但是好像超出时间限制
代码实现
void rotate(vector<int>& nums, int k) {
int length = nums.size();
k %= length;
if(k == 0) {return;}//如果k等于0或者k原本是等于len的，那么就相当于没有移动嘛，直接返回
//每次往后移一位，移动k次
for(int i = 0; i < k; ++i){
int temp = nums[length - 1];
for(int j = length - 1; j > 0; --j){
nums[j] = nums[j-1];
}
nums[0] = temp;
}
}
思路2
不再是每次循环1位，循环移动K次，直接一次移动到位，可以在O(n)时间完成，不过需要额外的k个空间保存元素即先将最后k个元素保存，因为下面移动将覆盖，然后直接一次移动k位放到正确位置，最后将最后k个元素放到最初正确位置
代码实现
void rotate(vector<int>& nums, int k){
int length = nums.size();
k %= length;
if(k == 0) {return;}//如果k等于0或者k原本是等于len的，那么就相当于没有移动嘛，直接返回
int tmp[k];
for(int i = 0; i < k; ++i){//先将最后k个元素保存，因为下面移动将覆盖
tmp[i] = nums[length - k + i];
}
for(int i = length-1; i >= k; --i){//直接一次移动k位
nums[i] = nums[i - k];
}
for(int i = 0; i < k; ++i){//将最后k个元素放到最初正确位置
nums[i] = tmp[i];
}
}
思路3
申请一个额外的数组，用来保存移动后的元素，不过这种方法时间复杂度O(n),空间复杂度O(n),最后将全部移动后的元素复制原数组
代码实现
void rotate(vector<int>& nums, int k){
int length = nums.size();
k %= length;
if(k == 0) {return;}//如果k等于0或者k原本是等于len的，那么就相当于没有移动嘛，直接返回
int tmp[length]; //额外申请一个数组，保存移动后元素
for(int i = 0; i < length; ++i){
tmp[(i+k)%length] = nums[i];
}
for(int i = 0; i < length; ++i){
nums[i] = tmp[i];
}
}