原題：
給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置砚亭，其中 k 是非負(fù)數(shù)。
示例 1:
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋:
向右旋轉(zhuǎn) 1 步: [99,-1,-100,3]
向右旋轉(zhuǎn) 2 步: [3,99,-1,-100]
說(shuō)明:
盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個(gè)問(wèn)題震贵。
要求使用空間復(fù)雜度為 O(1) 的原地算法。
一刷（c）:
方法一：
每次都把最后一個(gè)元素取出嗅义，前面元素往后移屏歹，循環(huán)k次。
void rotate(int* nums, int numsSize, int k) {
int temp=0;
for(int i=0;i<k;i++){
temp=nums[numsSize-1];
for(int j=numsSize-2;j>=0;j--){
nums[j+1]=nums[j];
}
nums[0]=temp;
}
}
方法二：
參考了大佬做法之碗，先反轉(zhuǎn)前n-k個(gè)元素蝙眶，再反轉(zhuǎn)后k個(gè)元素，在全部反轉(zhuǎn)褪那，但應(yīng)注意numsSize<k這種情況幽纷。(這個(gè)反轉(zhuǎn)算法很六)
void re(int* nums, int start ,int end){
while(start<end){
int temp=nums[start];
nums[start++]=nums[end];
nums[end--]=temp;
}
}
void rotate(int* nums, int numsSize, int k) {
if(numsSize<k){
k=k%numsSize;
re(nums,0,numsSize-k-1);
re(nums,numsSize-k,numsSize-1);
re(nums,0,numsSize-1);
}else{
re(nums,0,numsSize-k-1);
re(nums,numsSize-k,numsSize-1);
re(nums,0,numsSize-1);
}
}
方法三：
利用(i+k)%numsSize從第一個(gè)開(kāi)始確定該元素旋轉(zhuǎn)后的位置，直到所有元素歸位博敬。
public void rotate2(int[] nums, int k) {
if (nums.length == 0 || (k %= nums.length) == 0) {
return;
}
int length = nums.length;
int start = 0;
int i = 0;
int cur = nums[i];
int cnt = 0;
while (cnt++ < length) {
i = (i + k) % length;
int t = nums[i];
nums[i] = cur;
if (i == start) {
++start;
++i;
cur = nums[i];
} else {
cur = t;
}
}
}
一刷（Java）：
方法一：
class Solution {
public void rotate(int[] nums, int k) {
int temp=0;
for(int i=0;i<k;i++){
temp= nums[nums.length-1];
for(int j=nums.length-2;j>=0;j--){
nums[j+1]=nums[j];
}
nums[0]=temp;
}
}
}
BB一句：
方法二 和方法三都感覺(jué)比較巧妙友浸，方法二的反轉(zhuǎn)函數(shù)有意思，記下偏窝。
