2.17 数组循环移位

题目：设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O(n)，且只允许使用两个附加变量。

 

分析：首先，容易忽略K>N的情况，好大一个陷阱啊，有木有TAT。再次，分享下本弱菜的错误思路，错得很经典 = =！

WA:不采用一次性连续移动整体的方法，每次只移动有关联的元素。例如第一次移动 temp←a[n]←a[n-k]←a[n-2*k]←a[n-3*k].....最后将temp赋值给最后一个数，

貌似是正确的，错在没意识到这些元素是并不一定是首尾相接的（即头元素、尾元素不一定隔着K个单位）！

 

还是学习下书本的神算法吧：假设原数组序列为abcd1234，要求循环右移4个单位，即要得到1234abcd，不难看出，其中2段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。可通过以下步骤完成：

1、逆序排列abcd： abcd1234→dcba1234

2、逆序排列1234：dcba1234→dcba4321

3、全部逆序：dcba4321→1234abcd

 

Code:

 

#include<iostream>
#include<algorithm>

using namespace std;

int a[1000];

void reverse(int b,int e)
{
    for(;b<e;b++,e--)
    {
        int t=a[b];
        a[b]=a[e];  
        a[e]=t;           
    }     
}

int main()
{
    int n,k;
    cin>>n>>k;
    k%=n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    reverse(0,n-k-1);
    reverse(n-k,n-1);
    reverse(0,n-1);
    
    for(int i=0;i<n;i++)
        cout<<a[i]<<"  ";
    cout<<endl;
    system("pause");
    return 0;
}