数组循环移位算法

给定一个数组，将其循环右移（或左移）k位，要求时间复杂度为O(N)，空间复杂度为O(1)。

原始问题

OJ系统可参考以下链接：

https://www.patest.cn/contests/pat-b-practise/1008

解题思路

先用几个简单的例子分析下：

原数组 ：1 2 3 4 5 6 7 8
右移1位：8 1 2 3 4 5 6 7
右移3位：6 7 8 1 2 3 4 5
右移7位：2 3 4 5 6 7 8 1

从中很容易看出，右移k位即是将数组最后k个元素与之前的元素整体交换位置。问题的关键就是如何不用辅助空间在线性时间内实现这一交换过程。

解决这一问题依赖于以下数学原理：

假设$X$、$Y$为两个序列，$X^T$代表其反转序列（即reverse），$XY$代表两个序列的拼接，则有以下结论：

$$(X^T)^T=X$$
$$(XY)^T=Y^TX^T$$

我们要实现的交换过程其实就是将$XY$变换为$YX$，根据以上公式有：

$$YX=(X^TY^T)^T$$

这就是所谓的经典三步翻转法。

根据以上原理很容易就可以写出代码，只需要注意两点：

1. 左移k位就相当于右移N-k位，故只需考虑一种情况即可；
2. 移位k位和移位k+N位结果完全相同，故只需考虑k % N的情况即可。

C++代码

// k为正代表右移，k为负代表左移
void ArrayShift(int A[], int N, int k) {
  if (k < 0) {
    k = -k;
    k %= N;
    k = N - k;
  } else {
    k %= N;
  }

  reverse(A, A + N - k);
  reverse(A + N - k, A + N);
  reverse(A, A + N);
}

其中reverse()函数实现反转数组，在C++中可以直接使用<algorithm>头文件中的reverse()函数来实现。若使用C语言，自行实现此函数即可，注意要正确处理当k=0时reverse(A+N, A+N)的情况。