LeetCode 189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?
解析：
数组循环移位问题。
解法1:
最简单的思路，对数组循环K次，首先取出最后一个元素赋给temp，将剩余元素前一个数值赋给后一个，最后将temp赋给首元素。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
void rotate(vector& nums, int k) {
if(nums.empty())
return;
int len = nums.size();
k = k % len;
int temp = 0;
while(k>0)
{
temp = nums[len-1];
for(int index = len -1; index >0; index –)
{
nums[index] = nums[index-1];
}
nums[0] = temp;
k –;
}
}
};
[/cc]
时间复杂度为O(KN)，运行超时，需要继续优化。
解法2:
观察移位前后的数组。
1,2,3,4,5,6,7 k=3,移位后为
5,6,7,1,2,3,4
发现移位后的数组起始可以分为前后两部分，5,6,7和1,2,3,4这两部分都是有序的。采用逆序的方式，3次逆序
a. 逆序1,2,3,4
4，3，2，1，5，6，7
b. 逆序5,6,7
4,3,2,1,7,6,5
c. 整体逆序
5,6,7,1,2,3,4
代码如下：
[cc lang=”C++”]
class Solution {
public:
void rotate(vector& nums, int k) {
if(nums.empty())
return;
int len = nums.size();
k = k % len;
int temp = 0;
reverse(nums, 0, len-1-k);
reverse(nums, len-k, len-1);
reverse(nums, 0, len-1);

}
void reverse(vector &nums, int begin, int end)
{
int temp = 0;
for(;begin <=end; begin ++,end--) { temp = nums[end]; nums[end] = nums[begin]; nums[begin] = temp; } } }; [/cc] 运行结果：