题目
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?
解析
题目是很好理解的，即是将数组旋转k步，达到目标数组。但是题目中说至少有3种方法，因此，在此提供3种思路。
最容易想到的一种方法是，旋转3步，即为平移三步，从数组末尾向前，每次循环平移一步，要保存最后一个元素的value，每步循环结束后将保存的value赋值给nums[0]；
第二种方法是以空间换时间。malloc一个和原数组长度相同的新数组newNums，先将原数组保存至newNums，然后再循环新数组计算位置并赋值回去，nums[(i + k) % numsSize] = newNums[i];，注意需要取余；
也可以采用部分赋值的方法，即从numsSize-k位置平分为两半，后面部分赋到新数组前面部分，前面部分赋到新数组后面部分。最后再memcpy新数组->原数组。这样做也可以。第三种方法是交换，如下演示。
1,2,3,4,5,6,7,8
k = 4
最终结果为5,6,7,8,1,2,3,4
（1）交换0 -> 3（3 = 8 - 4 -1，即前半部分），结果为
4,3,2,1,5,6,7,8
（2）交换4->7（后半部分），结果为
4,3,2,1,8,7,6,5
整体交换
5,6,7,8,1,2,3,4 -->最终结果
此处的交换为两个value之间的交换。
误区：级联计算位置并且赋值的方法是不对的，反例为1,2,3,4,5,6，k=2，使用级联计算位置会发现：
(0 + 2) % 6 = 2
(2 + 2) % 6 = 4
(4 + 2) % 6 = 0
回到0了，只计算了3个位置。因此这样做是不正确的。
代码（C语言）
// 方法1：平衡k步
void rotate(int* nums, int numsSize, int k) {
if (nums == NULL || numsSize == 0 || k == 0 || (k % numsSize == 0))
return ;
k = k % numsSize;
int firstNum = 0;
for (int i = 0; i < k; ++i) {
firstNum = nums[numsSize - 1];
for (int j = numsSize - 2; j >= 0; --j) {
nums[j + 1] = nums[j];
}
nums[0] = firstNum;
}
}
// 方法2：空间换时间
void rotate2(int* nums, int numsSize, int k) {
if (nums == NULL || numsSize == 0 || k == 0 || (k % numsSize == 0))
return ;
k = k % numsSize;
int* newNums = (int*)malloc(sizeof(int) * numsSize);
// store all nums to newNums array
for (int i = 0; i < numsSize; ++i) {
newNums[i] = nums[i];
}
// get new position and store back
for (int i = 0; i < numsSize; ++i) {
nums[(i + k) % numsSize] = newNums[i];
}
free(newNums);
}
// 方法3：循环交换
void reverseRotate(int* front, int* rear);
void rotate3(int* nums, int numsSize, int k) {
if (nums == NULL || numsSize == 0 || k == 0 || (k % numsSize == 0))
return ;
k = k % numsSize;
reverseRotate(&nums[0], &nums[numsSize - k - 1]);
reverseRotate(&nums[numsSize - k], &nums[numsSize - 1]);
reverseRotate(&nums[0], &nums[numsSize - 1]);
}
void reverseRotate(int* front, int* rear) {
if (front == NULL || rear == NULL)
return ;
while (front < rear) {
int tempInt = (*front);
(*front) = (*rear);
(*rear) = tempInt;
++front;
--rear;
}
}
