首页 > 代码库 > 数组循环右移问题
数组循环右移问题
首先，假设我们有一个具有6个元素的数组： 1，2，3，4，5，6
现在我们要对这个数组循环右移4次，我们很直接很够推出它的结果是：3，4，5，6，1，2 。但是我们如何去实现这样一个问题呢?
我觉得大家最容易想到的方法就是：
step1：保存好数组中最后一个元素的值
step2：从第一个元素到倒数第二个元素依次向右移动一个位置
step3：然后将刚保存的值放到空出来的数组第一个位置
虽然这个方法想起来很简单，但是它的效率却不是很高，它的时间复杂度是O(n^2)。
现在，我再介绍一种效率较高的算法，这个算法，充分利用了模数求余的特点。
这种算法的时间复杂度是O(n)，比上一种算法效率有了很大的提高。
它的主要实现步骤是这样的：（记移动次数为move）
step1:初始化时，将pre_value初始化为数组的第一个元素
step2:从某个位置A(初始时A为0)开始开始（这里的A，B......指的是数组的下标所标志的位置），将pre_value复制到临时变量temp中，位置A加上移动的次数得到新的位置
B = A+move，
step3:保存位置B原来的数据到pre_value中，再将变量temp中的值复制到位置B中
step4:重复上述步骤step2，step3 N次（N为数组的长度），将所有的元素都更新到正确的位置后，就可以得到正确的移位后的数组。
但是在这里我们要注意到这样一个问题，可能存在这样的一种情况
例如：将数组1，2，3，4，5，6 利用上诉算法循环右移3次，得到的结果将是
这里我们看到这里形成了一个只有两个元素的环，并没有包括所有的元素，所以经过推算，我们得到这样两种情况下，应该作特殊处理，
情况一：移位次数是偶数
情况二：数组长度%移位次数 == 0的情况
解决的办法就是将一次移位动作划分为多次不含上述两种情况的移位动作，比如将一次偶数次的移位动作分解成先进行n-1次奇数次移位，再接着进行1次移位。
(注意：千万要注意第二种情况的问题)
下面就是我实现的代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 //该函数对于数组长度为偶数且移位的次数也为偶数情况不适用,对于数组长度能整除移位次数的情况也要另加考虑 5 //所以，对于偶数的情况，我们要分解成先移动count-1+1的组合 6 void BufferRightShift(int buffer[],int n,int count) 7 { 8 int i,j; 9 int temp,pre_value;10 pre_value = http://www.mamicode.com/buffer[0];11 if(count == 0)12 return;13 for(i=0,j=0;i<n;i++)14 {15 temp = pre_value;16 pre_value = http://www.mamicode.com/buffer[(j+count)%n];17 buffer[(j+count)%n] = temp;18 j = (j+count)%n;19 }20 }21 22 23 void ROR(int buffer[],int n,int count)24 {25 int move = count%n;26 if((move%2 == 0)||(n%move == 0)) //存在上面分析到的两种情况自已的处理方法27 {28 int k = 1;29 int i = move;30 while(1)31 {32 if(i == 1)33 break;34 if((i%2 == 0) || (n%i == 0)) //统计将移位次数分解成不再出现上述两种问题的次数35 {36 k++;37 i--;38 }39 else 40 break;41 }42 BufferRightShift(buffer,n,move-k);43 for(i=1;i<=k;i++)44 BufferRightShift(buffer,n,1);45 46 }47 else48 {49 BufferRightShift(buffer,n,move);50 }51 }52 53 int main()54 {55 int n,count,i;56 int *a;57 while(scanf("%d%d",&n,&count)!=EOF)58 {59 a = (int*)malloc(n*sizeof(int)); 60 for(i=0;i<n;i++)61 scanf("%d",&a[i]);62 63 ROR(a,n,count); 64 65 for(i=0;i<n-1;i++)66 {67 printf("%d ",a[i]);68 }69 printf("%d\n",a[n-1]);70 free((void*)a);71 }72 return 0;73 74 }
运行结果：
数组循环右移问题