数组右移 O(n) 只用一个辅助空间

 假设有个数组A[N]  

要把A 的元素循环右移k 位,则

A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].        然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去]

.分析可知,当n 和k 的最大公约数为p 时,只要分别以A[0],A[1],...A[p-1]为起点执行上述移动,就可以保证每一个元素都被且仅被右移一次

假设有两个数 a b  (a&&b>=1),设a b的最大公因数为C  则从0----max(a,b)的数轴上 可以最少地平均分成max(a,b)/C个部分 且 a,b都为断点 即a b 处都是被分割的点

 eg  在0---max(a,b)的数轴上 

0     1 23 a 5 b  

假设b>a      a为4   b为6   则C为2      也就是说从0开始向数轴正方向行走  

每C=2个格子走一步 可以以最少的步数同时经过a=4  b=6  走过的地方即为断点

  因为格子被最少平均分成了max(4,6)/C  =3个大格子  每一个大格子的数的数量其他的大格子的数的数量  相等且一一对应

只要分别以0,1,为起点执行向右移动C格 就可以保证每一个元素都被且仅被右移一次

# include <stdio.h># define N 13   //如果想录入x个字节那么就把N的数值改成x+1void LYn(int *A,int m,int n);//把数组A[m]的元素右移N位int main(){	int A[N]={0},i;	for(i=0;i<N;i++)	{		A[i]=N*i;		PRintf("%4d ",A[i]);	}    LYn(A,N,4);	printf("/n左移%d位后:/n",4);    for(i=0;i<N;i++)		printf("%4d ",A[i]);	LYn(A,N,N-4);	printf("/n右移%d位后:/n",N-4);    for(i=0;i<N;i++)		printf("%4d ",A[i]);    return 0;}void LYn(int *A,int m,int k)//把数组A[m]的元素右移N位{	int i,j,p,l,temp;    for(i=1;i<=k;i++)		if(m%i==0&&k%i==0) p=i;//求n 和k 的最大公约数p		for(i=0;i<p;i++)		{			j=i;			l=(i+k)%m;			while(l!=i)			{				temp=A[l];   //交换l j				A[l]=A[j];				A[j]=temp; 				j=l;    //刷新j  l 				l=(j+k)%m;			}// 循环右移一步			//for		}}代码 我就不简化了  记住这个方法就行 其他方法更不用说  有的是  只是在此说明此方法  仅此而已