【数组】旋转数组

做题思路：

1. 写出将数组向右旋转1步的算法，然后遍历三次
2. 设立一个int型temp存储数组最后一位元素。将数组所有元素依次向后替换，最后将第一位元素替换为最后一位元素

超出时间限制

void rotate(int* nums, int numsSize, int k){
    if(numsSize==1)
        return;
    for(int i = 0;i < k;i++) {
        int temp2 = nums[0];
        int temp3 = 0;
        for(int i = 1;i < numsSize;i++) {
            temp3 = nums[i];
            nums[i] = temp2;
            temp2 = temp3;
        }
        nums[0] = temp3;
    }
}

官方思路1：

1. 设置一个temp数组，将全部元素放进去
2. 用for循环遍历，将第temp[i]放入arr[(i+k)%numsSize]中

void rotate(int* nums, int numsSize, int k){
    if(numsSize==1)
        return;
    k %= numsSize;
    int* arr=(int*)malloc(numsSize*sizeof(int));
    int i = 0;
    for(i = 0;i < numsSize;i++) {
        if(i-k<0)
            arr[i] = nums[i-k+numsSize];
        else
            arr[i] = nums[i-k];
    }
    for(i = 0;i < numsSize;i++)
        nums[i] = arr[i];
}

官方思路2：

1. 右旋转k位，就是将数组最后k位元素放到数组最前面，然后前面的元素后移
2. 可以先将数组反转。
3. 再反转前k位，这样就得到了原数组的最后k位元素
4. 再反转从k+1到numsSize-1的元素，这样数组就完成

void reverse(int*nums, int start, int end) {
    while(start < end) {
        int temp = nums[end];
        nums[end] = nums[start];
        nums[start] = temp;
        start++; end--;
    }
}

void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    reverse(nums, 0, numsSize-k-1);
    reverse(nums, numsSize-k, numsSize-1);
    reverse(nums, 0, numsSize-1);
}