版权声明：转载请联系本人，感谢配合！本站地址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50600861
翻译
通过K步将一个有着n个元素的数组旋转到右侧。
例如，
给定n = 7和k = 3，数组[1,2,3,4,5,6,7]会被旋转成[5,6,7,1,2,3,4]。
批注：
尽你可能尝试多种解决方案，这里至少存在3种不同的方式去解决这个问题。原文
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.分析
第一种方法
我所想到的第一种方式是另设置一个vector，然后逐个元素添加进去，最后将这个vector赋值给nums。添加方式为将右边的k个元素添加进去，再将左边的n-k个元素添加进去。
具体代码为：
void rotate(vector<int> &nums, int k) {
if (nums.size() == 1) return;
if (k > nums.size()) k %= nums.size();
vector<int> newNums;
for (int i = nums.size() - k; i < nums.size(); ++i)
newNums.push_back(nums[i]);
for (int i = 0; i < nums.size() - k; ++i)
newNums.push_back(nums[i]);
nums = newNums;
}
Runtime: 28 ms超时方法
还有一个最简单的方法，不过妥妥的超时了……
void rotate(vector<int> &nums, int k) {
if (nums.size() <= 1) return;
if (k > nums.size()) k %= nums.size();
while (k > 0) {
int temp = nums[nums.size() - 1];
for (int i = nums.size() -1; i >0; --i) {
nums[i] = nums[i - 1];
}
nums[0] = temp;
k--;
}
}
Time Limit Exceeded第二种方法
上面那种方法不行，继续改进第一种方法。同样是将vector切成左右两边。
void rotate(vector<int> &nums, int k) {
if (nums.size() <= 1) return;
if (k > nums.size()) k %= nums.size();
vector<int> extra(nums.begin(), nums.begin() + nums.size() - k);
nums.erase(nums.begin(), nums.begin() + nums.size() - k);
nums.insert(nums.end(), extra.begin(), extra.end());
}
Runtime: 28 ms第二种方法改进
试试颠倒顺序呢？
void rotate(vector<int> &nums, int k) {
if (nums.size() <= 1) return;
if (k > nums.size()) k %= nums.size();
vector<int> extra(nums.end() - k, nums.end());
nums.erase(nums.end() - k, nums.end());
nums.insert(nums.begin(), extra.begin(), extra.end());
}
Runtime: 24 ms要少了4秒呢。
第三种方法
还有一种方法，可以使用STL自带的rotate()函数……
void rotate(vector<int>& nums, int k) {
int len = nums.size();
if (len > 1) {
k %= len;
std::rotate(nums.begin(), nums.end() - k, nums.end());
}
}
