原地数组循环移位

原题

本题要求实现一个对数组进行循环右移的简单函数：-一个数组a中存有n（> 0）个整数，将每个整数循环向右移m（≥0）个位置，即将a中的数据由$\left(a_{0} a_{1} \cdots a_{n-1}\right)$变换为$\left(a_{n-m} \cdots a_{n-1} a_{0} a_{1} \cdots a_{n-m-1}\right)$（最后m个数循环移至最前面的m个位置）。

函数接口定义：

1

int ArrayShift( int a[], int n, int m );

其中a[]是用户传入的数组；I n是数组的大小；m 是右移的位数。函数ArrayShift 须将循环右移后的数组仍然存在a[]中。

难度++

这本来是一道入门题，简单的做法只要开一个辅助数组然后取模计算移位后的位置即可。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int ArrayShift(int a[], int n, int m)
{
    m%=n;
	int b[MAXN],i;
	for (i=0; i<n;++i)
	{
		b[i] = a[(i - m + n) % n];
	}
	for (i = 0; i < n; ++i)
		a[i] = b[i];
	return 0;
}

然后我想着加大难度，既然与取模有关，那么应该有可以不开辅助数组的方法，那么就可以实现原地循环移位，大大降低空间复杂度。

分析

首先按照原来的算法，对于每一个位置i的数，我们都可以算出移位后它的目标位置(i+m)%n，但是如果不开辅助数组的话就存在覆盖的问题，即i位置的数要放在(i+m)%n的位置，但是不能将(i+m)%n位置原来的数直接覆盖掉——因为你没有备份，而那个位置的数还要移到(i+m+m)%n。那么在这样一个跳跃的过程中一个临时变量是必不可少的：用来存放当前正在跳跃的数。在交换的过程中还要一个辅助变量。这就好比手动操作这个过程，要先将第一个位置的数拿到手里，再将手中的数和下一个位置的数交换，一直重复这个过程。这里“手”就相当于一个临时变量，而且一只手肯定完成不了交换的过程（不行你试试），那么另一只手就是交换中使用的临时变量。

所以这样就形成了一个跳跃的循环链。但是这样会 存在一个问题，从0号位置开始这样不断跳跃，最终一定会回到0位置，但是不一定会经过0~n中所有的数。

使用计数器的解决办法

一种解决办法是，引入一个计数器，每跳跃一次计数器加一，一次循环结束后如果还没有遍历过1号位置，将起始位置后移，即从1号位置开始继续下一次循环，如此重复直到计数器的值为n为止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int ArrayShift(int a[], int n, int m)
{
    m%=n;
    #define nxt(x)(x+m)%n 
	for(int i=0,cnt=0;cnt<n;i++)
	{
		int j,tmp;
		for(j=nxt(i),tmp=a[i];j!=i;j=nxt(j))
		{
			int tt=a[j];
			a[j]=tmp;
			tmp=tt;
            ++cnt;
		}
		a[i]=tmp;
        ++cnt;
	}
	return 0;
}

进一步思考

上面这样的做法已经能够解决问题。但是因为每次循环的次数靠计数器来决定，虽然总时间复杂度仍然是O(n)，这样的算法还是不够优美直观。

假设起始位置是i,那么第一次跳跃的位置是(i+m)%n，第二次是(i+2m)%n，……第k次就是(i+km)%n。

我们先来考虑什么时候会跳回i，即(i+km)%n=i。

左=i%n+km%n=i+km%n，显然当km%n=0的时候跳回i，我们要做的就是找出满足这个式子的最小k。

设km=qn，要找出最小的k,q，就是相当于找出m,n的最小公倍数即lcm(m,n)=km=qn，k=lcm(m,n)/m=m*n/gcd(m,n)/m=n/gcd(m,n)

所以每次跳跃$k=\frac{n}{gcd(m,n)}$后就会回到i处。

那么一共需要跳跃的次数cnt=n/k=gcd(m,n)。

而且如果在第i位置开始的循环结束后还没有遍历所有的数，那么i+1位置的数一定属于没有被经过的集合，那么下一次从i+1开始就是合理的。

证明：

因为假设i位置开始的循环中经过了i+1，

有$i+1=(i+pm)\%n=i+pm\%n$，

消去i得到$pm\%n=1$，

那么从i+1开始的所有位置$(i+1+qm)\%n=i+1+pm\%n$，

将1用$pm\%n$替换，即$i+pm\%n+qm\%n=i+(p+q)m\%n$，

也就是说，所有i+1跳跃到的位置也是i开始能跳跃到的位置。

同样地，任意$(i+a+rm)\%n=i+a+rm\%n=i+a(pm\%n)+rm\%n\\=i+(ap+r)m\%n$，

那么之后的所有序列都已经包含在i开始的序列中了，

所以i这次循环就已经将所有没有遍历的数遍历了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int gcd(int a,int b)
{
	if(a==0)return b;
	if(b==0)return a;
	return gcd(b,a%b);
}
int ArrayShift(int a[], int n, int m)
{
    m%=n;
    #define nxt(x)(x+m)%n 
    int g=gcd(m,n);
	for(int i=0;i<g;++i)
	{
		int j,tmp;
		for(j=nxt(i),tmp=a[i];j!=i;j=nxt(j))
		{
			int tt=a[j];
			a[j]=tmp;
			tmp=tt;
		}
		a[i]=tmp;
	}
	return 0;
}

感谢

感谢@Zhangsl089对此题解法做出的重大贡献。