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.
设 数组长度为n，移动步数为k
思路整理：
1.是否能通过公式计算出移动后的位置呢？
解决：假设当前位置为 a0，则移动后的位置为 a1 = (a0 + k) % n;
2.如果我们让nums[a1] = nums[a0]，那么nums[a1]该怎么处理？
解决：可以计算a1位置移动后的下一个位置a2 = (a1 + k) % n，然后让nums[a2] = nums[a1]，依次类推，直到下一个位置an回到起点位置 也就是 a，这样循环下去，总会将所有元素替换掉吧。
3.我试着编写出一个循环程序，提交后发现程序存在严重漏洞，如果 n % k = 0 或者 k % n = 0，我们执行这个程序会发现不能移动所有元素，比如 n = 6，k = 3，执行的操作是a0->a3，a3->a0，我们会发现a1，a2...等元素并没有替换掉。那么该怎么处理这个问题呢？
解决：抓住n % k = 0 或者 k % n = 0这种情况做分析，我发现可以加入一层外层循环，还是上面例子，外层循环是 a0，a1，a2，这样就可以保证所有元素可以替换掉了。
4.外层循环的执行次数 c 该如何限制呢？
解决：我使用了归纳假设方法，首先假设n % k = 0，c = k；k % n = 0，c = n，其他情况的话 c = 1，这种假设经过程序测试，发现是错误的，假如n = 6， k = 4很明显还是不能遍历所有元素。然后我继续使用归纳方法，举出很多种n和k的组合，最后大胆的假设c是n和k的最大公约数，事实证明，这是正确的。也许这个结论证明并不严谨，但已经足够解决这个问题了。
写出程序如下：
void rotate(vector<int>& nums, int k) {
int n = nums.size();
if (n == || k == )
return;
// 求最大公约数
int a = n, c = k, b = a % c;
while (b != )
{
a = c;
c = b;
b = a % c;
}
// 依次替换
while (c--)
{
int oldNum = nums[c];
int curPos = (c + k) % n;
while (curPos != c)
{
int curNum = nums[curPos];
nums[curPos] = oldNum;
curPos = (curPos + k) % n;
oldNum = curNum;
}
nums[curPos] = oldNum;
}
}
这里要注意依次替换的时候，我们要使用一个临时变量oldNum来保存上一次被替换掉的元素。循环体内的赋值过程有些绕，要理清思绪。我在这里卡了一阵子，越想越头晕。。。
算法总结：
这个算法成功的将时间复杂度控制在O(n)，而且空间复杂度是O(1)，更可贵的是所有操作没有改变内存位置。可以说是非常理想了。
查看了下网上的其他方法，大体上有三种，
一种是将所有元素从后往前依次移动一个位置，然后外层循环k次。这种方法时间复杂度为O(n*k)，不消说，没有多少效率。
代表算法（C语言实现）：
void rotate(int nums[], int n, int k) {
int temp;
for (int step = ; step < k; step++) {
temp = nums[n-];
for (int i = n-; i > ; --i)
{
nums[i] = nums[i-];
}
nums[] = temp;
}
}
一种是反转数组的方法，先把整个数组reverse，然后把前面的reverse回来，再把后面的reverse回来，代表算法：
void rotate(int nums[], int n, int k) {
k = k % n;
reverse(nums, nums + n);
reverse(nums, nums + k);
reverse(nums + k, nums + n);
}
这个算法比较高明，时间复杂度可以控制在O(n)，空间复杂度也是O(1)，非常理想，但要看你的reverse实现是否高效
还有一种方法个人认为比较投机取巧，它使用C语言的内存操作函数，改变了内存地址，有一定风险，但算法确实高效
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;
}
算法——让人类思维更加理性