題目
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?
解析
題目是很好理解的臭笆，即是將數(shù)組旋轉(zhuǎn)k步叙淌，達到目標數(shù)組秤掌。但是題目中說至少有3種方法，因此鹰霍，在此提供3種思路闻鉴。
最容易想到的一種方法是，旋轉(zhuǎn)3步茂洒，即為平移三步孟岛，從數(shù)組末尾向前，每次循環(huán)平移一步督勺，要保存最后一個元素的value蚀苛，每步循環(huán)結(jié)束后將保存的value賦值給nums[0]；
第二種方法是以空間換時間玷氏。malloc一個和原數(shù)組長度相同的新數(shù)組newNums堵未，先將原數(shù)組保存至newNums，然后再循環(huán)新數(shù)組計算位置并賦值回去盏触，nums[(i + k) % numsSize] = newNums[i];渗蟹，注意需要取余；
也可以采用部分賦值的方法赞辩，即從numsSize-k位置平分為兩半雌芽，后面部分賦到新數(shù)組前面部分，前面部分賦到新數(shù)組后面部分辨嗽。最后再memcpy新數(shù)組->原數(shù)組世落。這樣做也可以。第三種方法是交換糟需，如下演示屉佳。
1,2,3,4,5,6,7,8
k = 4
最終結(jié)果為5,6,7,8,1,2,3,4
（1）交換0 -> 3（3 = 8 - 4 -1，即前半部分）洲押，結(jié)果為
4,3,2,1,5,6,7,8
（2）交換4->7（后半部分）武花，結(jié)果為
4,3,2,1,8,7,6,5
整體交換
5,6,7,8,1,2,3,4 -->最終結(jié)果
此處的交換為兩個value之間的交換。
誤區(qū)：級聯(lián)計算位置并且賦值的方法是不對的杈帐，反例為1,2,3,4,5,6体箕，k=2，使用級聯(lián)計算位置會發(fā)現(xiàn)：
(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：循環(huán)交換
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;
}
}
