学步园

设计算法，把一个含有n个元素的数组循环右移k位，要求时间复杂度为O（n），只允许使用两个附加变量。

解法一：每次将数组中元素右移一位，这样算法能够实现移位，但是算法复杂度为O（k*n），代码如下：

 RightShift(int *arr,int n,int k)
 {
     while(k--)
     {
        int temp=a[n-1];
        for(int i=1;i<n;++i)
        { a[i]=a[i-1]; }
        a[0]=temp;
     }
 }

解法二：右移k位之后的情况跟右移k%n位之后的情况是一样的，算法复杂度为O（n*n），代码如下：

 RightShift(int* arr,int k,int n)
 {
     k=k%n;
     while(k--)
     {
        temp=a[n-1];
        for(int i=1;i<n;++i)
        { a[i]=a[i-1]; }
        a[0]=temp;
    }
 }

解法三：变换的过程通过以下步骤完成：

1. 逆序排列abcd：abcd1234 → dcba1234；

2. 逆序排列1234：dcba1234 → dcba4321；

3. 全部逆序：dcba4321 → 1234abcd

代码如下：

  Reverse(int* arr,int b,int e)
  {
     for(;b<e;b++,e--)
     {
        int temp=arr[e];
        arr[e]=arr[b];
        arr[b]=temp;
     }
  }
 RightShift(int* arr,int n,int k)
 {
    k=k%n;
    Reverse(arr,0,n-k-1);
    Reverse(arr,n-k,n-1);
    Reverse(arr,o,n-1);
 }