旋转数组

原题：

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

要求使用空间复杂度为 O(1) 的原地算法。

一刷（c）:

方法一：

每次都把最后一个元素取出，前面元素往后移，循环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;
    }
}

方法二：

参考了大佬做法，先反转前n-k个元素，再反转后k个元素，在全部反转，但应注意numsSize<k这种情况。(这个反转算法很六)

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从第一个开始确定该元素旋转后的位置，直到所有元素归位。

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一句：

方法二 和方法三都感觉比较巧妙，方法二的反转函数有意思，记下。