题目要求:
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.
Hint:
Could you do it in-place with O(1) extra space?
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
这道题要注意的是:k可能比数组的大小还大。程序如下:
class Solution {
public:
void permute(vector<int>& nums, int start, int end)
{
if(start > end)
return; int sz = (end - start) / + ;
for(int i = ; i < sz; i++)
{
int tmp = nums[start+i];
nums[start+i] = nums[end-i];
nums[end-i] = tmp;
}
} void rotate(vector<int>& nums, int k) {
int sz = nums.size();
if(sz <= k)
k -= sz;
if(k == )
return;
permute(nums, , sz - k - );
permute(nums, sz - k, sz - );
permute(nums, , sz - );
}
};