编程之美 2.17 ：数组循环移位 (199)

题干

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

原数组：abcdefg

右移动3位：efgabcd

我的解答

思路

首先，如果k=1，也就是循环移动1位，那我们将有从后往前遍历一次即可。使用一个变量循环，另一个变量作储存最后一个数组元素。

当然，上面的思路只能针对k=1的情况。

第二个思路是，如果给了我k，那么其实我已经直接知道每一个数组元素最终的位置了，那么我针对每一个数组元素，算出其最终位置，将其放置即可。我的想法确实是实现了，我认为也确实是只遍历了一遍，但是额外用的变量还比较多。具体请看下面的代码吧。

代码

#include <stdio.h>


/*将长度为length的数组a内的每个元素，向右移动k个*/
void RightShift(int *a,int length,int k){
	int tmp1,tmp2;//使用两个临时变量来放置元素的数据

	int n=length;//重复次数
	int i=0;//从下标为0的元素开始

	tmp1=a[0];
	while(n--){
		int x=i+k;
		x=x%length;//防止越界
		tmp2=a[x];
		a[x]=tmp1;
		tmp1=tmp2;
		i=x;
	}

}

/*为了测试而封装的方法，主要是打印*/
void test(int *a,int length,int k){
	int i;

	printf(" 移动前：");
	for(i=0;i<length;i++){
		printf(" %d",a[i]);
	}
	printf("\n");
	RightShift(a,length,k);
	printf("右移%d个：",k);
	for(i=0;i<length;i++)
	printf(" %d",a[i]);
	printf("\n");
}


int main(){
	int length;
	int k[]={0,1,2,3,4,5,6,8};//k数组用于存放将要右移的位数

	/*设计测试的用例：*/
	int i;//循环试试k里面的所有的变量
	for(i=0;i<sizeof(k)/sizeof(k[0]);i++){
		int a[]={0,1,2,3,4,5,6};//正常的一个
		length=sizeof(a)/sizeof(a[0]);
		test(a,length,k[i]);
	}

	for(i=0;i<sizeof(k)/sizeof(k[0]);i++){
		int a[]={0};//只有一个0的
		length=sizeof(a)/sizeof(a[0]);
		test(a,length,k[i]);
	}


	for(i=0;i<sizeof(k)/sizeof(k[0]);i++){
		int a[2]={};//如果数组为空的话，会不会报错
		length=sizeof(a)/sizeof(a[0]);
		test(a,length,k[i]);
	}

}
           

运行结果

[email protected]:~/workspace/test/src$ ./a.out 
 移动前： 0 1 2 3 4 5 6
右移0个： 0 1 2 3 4 5 6
 移动前： 0 1 2 3 4 5 6
右移1个： 6 0 1 2 3 4 5
 移动前： 0 1 2 3 4 5 6
右移2个： 5 6 0 1 2 3 4
 移动前： 0 1 2 3 4 5 6
右移3个： 4 5 6 0 1 2 3
 移动前： 0 1 2 3 4 5 6
右移4个： 3 4 5 6 0 1 2
 移动前： 0 1 2 3 4 5 6
右移5个： 2 3 4 5 6 0 1
 移动前： 0 1 2 3 4 5 6
右移6个： 1 2 3 4 5 6 0
 移动前： 0 1 2 3 4 5 6
右移8个： 6 0 1 2 3 4 5
 移动前： 0
右移0个： 0
 移动前： 0
右移1个： 0
 移动前： 0
右移2个： 0
 移动前： 0
右移3个： 0
 移动前： 0
右移4个： 0
 移动前： 0
右移5个： 0
 移动前： 0
右移6个： 0
 移动前： 0
右移8个： 0
 移动前： 0 0
右移0个： 0 0
 移动前： 0 0
右移1个： 0 0
 移动前： 0 0
右移2个： 0 0
 移动前： 0 0
右移3个： 0 0
 移动前： 0 0
右移4个： 0 0
 移动前： 0 0
右移5个： 0 0
 移动前： 0 0
右移6个： 0 0
 移动前： 0 0
右移8个： 0 0
           

书上的解答

反转字符串三次，也许很巧妙，但是你看完下面的变化之后会觉得很神奇。

abcd1234，要求右移四位，变成1234abcd。

1. 先逆序abcd：abcd1234 成为dcba1234
2. 再逆序1234：dcba1234 成为 dcba4321
3. 全部逆序：dcba4321成为 1234abcd

确实很奇怪，发现的人应该很厉害吧。

上面的解释有歧义，请看下面的反转过程：

原数组：abcdefg

右移动3位：efgabcd

变化过程：

1. 将后3位反转：abcd gfe
2. 将除了后3位的反转：dcba gfe
3. 全部反转：efgabcd