题目来源
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.
第一种最简单的方法呢，是直接创建另一个数组，然后rotate之后再赋值回去。
如下：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> nums2(n, 0);
k = k % n;
for (int i=0; i<n; i++) {
nums2[i] = nums[(i-k + n) % n];
}
for (int i=0; i<n; i++)
nums[i] = nums2[i];
}
};
这种方法需要O(n)的空间和复杂度。想想怎么改进，想了想，反转3次就可以了，代码如下，只需要O(1)的空间。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
if (k != 0) {
reverse(nums.begin(), nums.begin()+n-k);
reverse(nums.begin()+n-k, nums.end());
reverse(nums.begin(), nums.end());
}
}
};
需要注意的是reverse的开始指的是第一个元素，结束指的是结束元素的下一个位置。
