轮转数组(力扣)

思路一：时间复杂度（往往考虑最坏的情况）为O(n^2)  （最坏情况下 K*M =（N-1）*N）

void rotate(int* nums, int numsSize, int k) 
{   
    //针对k>numsSize的情况
    //思路1，创建一个临时变量，存放要旋转的数组值
    k%=numsSize;
    //表示要旋转多少次
    while(k--)
    {   
        int tmp = nums[numsSize-1];
        //整体数组往后退一个  在尾部往前后退  而不是在首部,否则会出现数组中的数很多一样，重覆盖
        for(int i = numsSize-2;i>=0;i--)
        {
            nums[i+1]=nums[i];
        }
        nums[0]=tmp;
    }
}

思路二:先前n-k个逆置，在后k个逆置，最后整体逆置

//实现数组的逆置
void reverse(int*arr,int left,int right)
{
    while(left<right)
    {
        int tmp=arr[left];
        arr[left]=arr[right];
        arr[right]=tmp;
        left++;
        right--;
    }

}

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