数组循环移位算法

给定一个数组,将其循环右移(或左移)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++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 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=0reverse(A+N, A+N)的情况。

文章目录
  1. 1. 原始问题
  2. 2. 解题思路
  3. 3. C++代码