线性表循环移位

这是一道经典算法题

将数组中An中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换的次数为
O(n)。

解读

题目的意思很容易理解，即将数组中所有元素循环右移k位。比如，abcd1234循环右移4位为1234abcd。其中要求时间复杂度为O(n),空间复杂度为O(1)。

解法

经典算法

先将前 n-k 个元素倒置，即为dcba1234
再将后面所有剩余元素倒置，即为dcba4321
最后将整体所有元素倒置，即为1234abcd

公式为：
XY->YX = (X-1Y-1)-1，其中-1为倒置

毫无疑问，此解法最佳。代码略。

另一算法

此算法原先是笔者认真思考得来，符合题目要求。后来经过网上求证，无独有偶，发现相似的算法，而且更加详细精密。

笔者思路

时间复杂度要为O(n)，每个元素必须只能移动一次，即i元素只能一次移动到(i+k)%n元素的位置上
移动时(i+k)%n元素必须缓存起来
为原来的(i+k)%n元素进行移动操作，移动到
(i+2k)%n元素的位置上
缓存(i+2k)%n元素
如此重复

void rightShift(int a[], int n, int k) {
    //移动k位和k%n位是一致的
    if(!(k=k%n)) return;
    int temp;
    //初始化，从第一个元素开始
    int j = 0;
    int buff = a[j];
    for (int i = 0; i < n; ++i) {
        j = (j+k)%n;
        temp = a[j];
        a[j] = buff;
        //将第(j+k)%n元素存入buff
        buff = temp;
    }
}

你会发现以上算法的结果可能是错的。比如n=4，k=2的时候，它只会为其中两个元素进行移位，即第0号元素和第2号元素。下面进行修正。

void rightShift(int a[], int n, int k) {
    //移动k位和k%n位是一致的
    if(!(k=k%n)) return;
    int temp;
    //初始化，从第一个元素开始
    int j = 0;
    int s = j;
    int buff = a[j];
    for (int i = 0; i < n; ++i) {
        j = (j+k)%n;
        temp = a[j];
        a[j] = buff;
        //将第(j+k)%n元素存入buff
        buff = temp;
        //重复修正,进入下个循环群
        if(j == s) {
            j = (j+1)%n;
            s = j;
            buff = a[j];
        }
    }
}

网上某文章对于此问题的详细解答

如刚才所提到的，当n=4，k=2时，第一个程序只会为A[0]、A[2]进行移位，并且重复1次，刚好共移动了4次。因此A[1]、A[3]原封不动，未到达正确位置。

此情况的循环群有两个0、2和1、3，第一个程序只进入第一个循环群却没有进入另外一个，因此要进行重复修正。经过推算，我们可以得知循环群的个数则为k、n的最大公约数。比如n=10，k=3时循环群数为1，则不需要进行重复修正。此结论可以通过重复修正的次数进行验证。

Reference

数组循环移位，你能想到多少种算法？