189. 旋轉陣列

給定一個陣列，將陣列中的元素向右移動 k 個位置，其中 k 是非負數，

進階：

盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題，
你可以使用空間復雜度為 O(1) 的 原地 演算法解決這個問題嗎？

示例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉 1 步: [7,1,2,3,4,5,6]
向右旋轉 2 步: [6,7,1,2,3,4,5]
向右旋轉 3 步: [5,6,7,1,2,3,4]
示例 2:

輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋:
向右旋轉 1 步: [99,-1,-100,3]
向右旋轉 2 步: [3,99,-1,-100]

解法一：暴力求解（依次旋轉K輪）

思想：每次旋轉一個數字，將其他N-1個資料依次挪動，K個資料就K次，（超時）

//方法一：暴力法（k次旋轉法）---超時，
    //---------------------------------
    /*k=k%numsSize;
    int temp=0;
    for(int i=0;i<k;i++)
    {
        temp=nums[numsSize-1];
        for(int j=numsSize-1;j>0;j--)
        {
            nums[j]=nums[j-1];
        }
        nums[0]=temp;
    }*/
    //---------------------------------

解法二：額外空間法

思想: 申請額外k個空間arr，存放原陣列 后k 個資料，再往右挪動原陣列的資料k步，再將arr填充到 前n-k 個資料里，

 //方法2：額外空間法
    //申請額外k個空間arr，存放原陣列 后k 個資料
    //再往右挪動原陣列的資料k步，再將arr填充到 前n-k 個資料里，
    k=k%numsSize;
    int *arr=(int *)malloc(k*sizeof(nums[0]));
    if(arr!=NULL)
    {
    int Size=0;
    for(int i=numsSize-k;i<numsSize;i++)
    {
        *(arr+Size)=nums[i];
        Size++;
    }
    for(int j=numsSize-1-k;j>=0;j--)
    {
        nums[j+k]=nums[j];
    }
    for(int m=0;m<k;m++)
    {
        nums[m]=*(arr+m);
    }   
    }
    //可以申請好k個int的空間，然后用三次memcpy搞定，

解法三：三次翻轉

思想：
第一次：將整個陣列翻轉逆置，
第二次：將前K個資料翻轉逆置，
第三次：將后面一組n-k個資料翻轉逆置，

void reverse(int *arr, int arrSize)
{
	int temp = 0; 
	arrSize = arrSize - 1;
	for (int i = 0; i < arrSize / 2 + arrSize % 2; i++)
	{
		temp = *(arr + arrSize - i);
		*(arr + arrSize - i) = *(arr + i);
		*(arr + i) = temp;
	}
}
  //方法四：三次反轉
    k=k%numsSize;
    //第一次反轉：整個陣列反轉，
    reverse(nums,numsSize);
    //第二次反轉：反轉k個數字，
    reverse(nums,k);
    //第三次反轉：反轉numsize-k個，
    reverse(nums+k,numsSize-k);

解法四：環狀替換

遞回法

先看下面這種交換方式：

替換線指向的是對應數字，不是對應位置！！！

交換完成后，就是旋轉2次的結果，5，6，1，2，3，4，
再來看下面這種：

代碼：

  //方法三：環狀替換
    //遞回法
    //-------------------------------------------------
k=k%numsSize;
if(k==0)
{
    return ;
}
int times=0;
while(times<k)
{
    for(int i=times;i<numsSize;i+=k)
    {
        if(i+k<numsSize)
        {
            swap(&nums[times],&nums[i+k]); 
        }
        else
        {
            break;
        }
    }
    times++;
}
int nextk=0;
if(numsSize%k==0)
{
    return;
}
else
{
    nextk=k-numsSize%k;
    rotate(nums,k,nextk);
}
    //-------------------------------------------------

回圈迭代法

遞回法是先旋轉，消除余數，
而回圈迭代法，我們直接求n和k的最大公約數count，分count組，直接消除余數的存在，最后一個替換數字的下一個（會陣列越界，取余數拿到正確的陣列下標）就是該組的起始位置，首尾相接，一個組的替換完成退出，
外面再討厭一個回圈，控制組數，
圖解：

代碼：

void swap(int *num1,int *num2)
{
    int temp=*num1;
    *num1=*num2;
    *num2=temp;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 //回圈迭代法
    //-------------------------------------------------
    k=k%numsSize;
    if(k==0)
    {
        return ;
    }
    int count=gcd(numsSize,k);
    int group=0;
    while(group<count)
    {
        for(int i=group+k;1;i+=k)  //group下標是每組的第一個下標，用第一個位置保存下一個資料，不必再開單獨的空間，i+group則是要交換的位置下標
        {                          
            if(i%numsSize!=group)
            {
                swap(&nums[group],&nums[i%numsSize]); 
            }
            else
            {
                break;
            }
        }
        group++;
    }
    //-------------------------------------------------