Three methods to disassemble the rotation array

Title Description ： Give you an array , Rotate the elements in the array to the right  k  A place , among  k  It is a non negative number .

for example

Input : nums = [1,2,3,4,5,6,7], k = 3
Output : [5,6,7,1,2,3,4]
explain :
Rotate right 1 Step : [7,1,2,3,4,5,6]
Rotate right 2 Step : [6,7,1,2,3,4,5]
Rotate right 3 Step : [5,6,7,1,2,3,4]

The first method I think of is violent choice Time complexity O(k*N)

When there is no clear statement k Value According to the worst-case principle Its time complexity Should be O(N^2)

Then there is no suspense about the result The result is beyond Time limit . Here is my code Easy to understand There's not much to explain ;

void rotate(int* nums, int numsSize, int k){
    int i = 0;
    int j = 0;
    for (i = 0; i < k; i++)
    {
        int tmp = nums[numsSize - 1];
        for (j = numsSize-1; j > 0; j--)
        {
            nums[j] = nums[j - 1];
        }
        nums[0] = tmp;
    }
    return nums;
}

1. Use extra arrays

Exchange extra space for time ; Open up additional arrays For storage .

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

2. How to invert an array

Three reverses  

for example

Array              1 2 3 4 5 6 7  k = 3

The first step is to reverse   7 6 5 4 3 2 1

Step 2 reverse   5 6 7 4 3 2 1

Step 3 reverse   5 6 7 4 1 2 3

void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}

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

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

3. I'll study it again