Leetcode daily practice: rotating arrays

link : Rotated array

Ask us to transfer , Is to move the last number to the front , Then keep the other numbers in order and move one step back .

Conventional thinking ： Just use while loop , The title requires us to rotate n Time , We'll be back n Move the numbers to the front . Although this idea works , But think about it , Move the front number back each time , This time complexity is not low , So we won't talk about this conventional idea here .

New ideas ： The title requires us to rotate the array , In fact, we can First flip the entire array in order , then Before we move on n - 1 Number reversal order , Finally, after numsSize - n Number reversal order （ Suppose the number of arrays here is numsSize individual ）, In fact, the array rotation is completed .

notes ： Here's a key point , Namely If you flip n Time , and n Equal to the length of the array numsSize Words , In fact, the original array does not move , And so on , So we can n Do something about it .

And the spatial complexity of this idea is O(1) Of ！

Code ：

void partRotate(int* a, int left, int right)
{
    
    // Use left and right pointers 
    while(left < right)
    {
    
        int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;

        left++;
        right--;
    }
}

void rotate(int* nums, int numsSize, int k){
    
    k %= numsSize;
    // if k The finished length of the die is 0, Then there is no need to rotate 
    if(k == 0)
        return;

    partRotate(nums, 0, numsSize - 1);// First flip the entire array 

    partRotate(nums, 0, k - 1);// Then flip the front k - 1 individual 

    partRotate(nums, k, numsSize - 1);// Finally, after turning numsSize - k individual 
}