Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7]
is rotated to [5,6,7,1,2,3,4]
.
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.[show hint]
Hint:Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II
Solution 1:reverse[1,2,3,4]=[4,3,2,1], reverse[5,6,7]=[7,6,5], reverse[4,3,2,1,7,6,5]=[5,6,7,1,2,3,4]
#include<algorithm>
class Solution {
public:
void rotate(vector<int>& nums, int k) { //runtime:24ms
int n=nums.size();
k %= n;
reverse(nums.begin(),nums.begin()+n-k);
reverse(nums.begin()+n-k,nums.end());
reverse(nums.begin(),nums.end());
}
};
Solution 2:超时
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
k %= n;
while(k--){
int temp=nums[n-];
for(int i=n-;i>;i--){
nums[i]=nums[i-];
}
nums[]=temp;
}
}
};
Solution 3:
void rotate(int nums[], int n, int k) {
k = k % n;
if (k == ) return;
int *temp = new int[n];
memcpy(temp, nums+(n-k), sizeof(int)*k);
memcpy(temp+k, nums, sizeof(int)*(n-k));
memcpy(nums, temp, sizeof(int)*n);
delete[] temp;
}