void rotate(int* nums, int numsSize, int k){
    //这里是大一的做法，现在看当时的代码，不忍直视！太烂了
    //思路就是直接遍历，无论k的值为多少，都一个一个，一遍一遍的挪移。
    //一共挪动K次，每一次要滚动numSize次。。。
    for(int i=1;i<=k;i++)
    {
        //保存数组最后的值，然后从倒数第二个开始滚动
         int temp=nums[numsSize-1];
        for(int j=numsSize-1;j>0;j--)
        {
           
            nums[j]=nums[j-1];
        }
        //将最后一个滚动到数组头
        nums[0]=temp;
    }

}

void rotate(int* nums, int numsSize, int k){
    //新建数组
    int arr[numsSize];
    for(int i=0;i<numsSize;i++)
    {
        //直接将旋转元素放置新数组对应旋转后的位置
        arr[(k+i)%numsSize]=nums[i];
    }
     for(int i=0;i<numsSize;i++)
    {
         //然后在放回原数组，完成旋转
        nums[i]=arr[i];
    }
    

}

//交换两个数的值
void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

//数组转置
void overturn(int *arr,int frist,int last)
{
    while(frist<last)
    {
        swap(&arr[frist++],&arr[last--]);        
    }
}

//数组转置

void rotate(int* nums, int numsSize, int k){
    //求出滚动步长
    int flag=k%numsSize;
    //判断是否是周期性滚动
    if(flag)
    {
        //翻转整个数组
        overturn(nums,0,numsSize-1);
        //翻转前半部：0-k%numsSize-1,得到滚动后的排序
        overturn(nums,0,flag-1);
        //翻转后半部：k%numsSize-1-numsSize-1,使其回到正常的排
        overturn(nums,flag,numsSize-1);
    }
}

//递归求解最小n,k公约数
int gcd(int k, int n) {
    return n ? gcd(n, k % n) : k;
}

//交换两个数
void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
     //确定一趟遍历的次数
    int count = gcd(k, numsSize);
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = nums[start];
        do {
            int next = (current + k) % numsSize;           
            swap(&nums[next], &prev);
            current = next;
        } while (start != current);
    }
}