试分析如何把数组array中的所有元素循环右移p位

    昨天，一个考研的同学问我一算法问题。题目如下：     把数组array中的所有元素循环右移p位，要求时间复杂度为O(N)并且只能用一个临时存储变量。     初次拿到题目的时候，觉得此题非常简单，随即想出一个简单的算法，但一分析时间复杂度达到了O(p*N)，根本就不符合题目要求。再一考虑，觉得还是很简单，只要每次把p位之后的元素赋值给临时变量temp，p位之前的元素赋值过来就能实现元素的移动。具体操作过程如下：     例如数组为[0, 1, 2, 3, 4, 5, 6]，需要循环移动2位     (1). 0应该被移动到2的位置，所以首先把2放到temp中，0赋值到2中。这样就实现了0的移动。     (2). 2应该被移动到4的位置，但是此时不能直接把temp中保存的2的数据复制到4中，因为4的元素还没有保存。这也不难解决，可以先把4复制给0（反正0已经被保存到2了），再把temp中的值复制过来，最后把0中的数据赋回给temp。     (3). 然后按照(2)中的方法依次移动4,6,1,3,5 最终完成整个数组的移动。 　算法的整个访问链是: 0->2->4->6->1->3->5->0 结束     本以为算法到此就结束了，再稍作考虑又发现一个问题，那就是当数组的长度是移动的位数p的倍数时，上述算法就不再有效了。     如数组[0, 1, 2, 3]，移动2位，0中的数据需要移动到2中，2中的数据同时又恰巧需要移动到0中，这样就陷入了一个环，1,3中的数据没有机会被访问到。     这种情况访问链就变成了: 0->2->0 提前结束。这是一个很容易被忽视的问题。

    经仔细分析发现，这种情况不光在数组的长度是移动的位数p的倍数时存在，只要数组的长度和p之间存在1之外的公约数，这种情况就会存在，可见在数组循环移位中这种现象是非常普遍的。

    为了弄明白这里面的规律，我以数组[0:14]，p=6为例，手动进行了分析并得到以下结论：     [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]     整个数组可以分拆成3条访问链：     1.　　0->6 ->12 ->3 ->9 ->0     2.    1->7->13->4->10->1     3     2->8->14->5->11->2 　  至此数组中的所有元素都被访问到了且每条访问链均适用前面算法。那么怎么确定有几条访问链呢？我们发现访问链的条数3刚好是数组长度15和p=6的最大公约数。这样 访问链的循环次数也得到了。

    于是根据以上此路，我使用java编写了以下程序：

import java.util.Arrays;

/**
 * 
 * @author yang
 * 编写时间: 2011/08/15 21:31
 */
public class MoveArrayTest {
	/**
	 * 把数组array中的所有元素循环右移p位，要求时间复杂度为O(N)并且只能用一个临时存储变量。
	 * @param array		给定数组
	 * @param p		移动位数
	 * @return		返回移动后的数组
	 */
	public static int[] moveArray(int[] array, int p) {
		int k = 0;
		int size = array.length;	//数组大小
		
		// 计算数组大小size和移动次数p之间的最大公约数k
		for (int i = 1; i <= Math.min(size, p); i++) {
			if (size % i == 0 && p % i == 0)
				k = i;
		}
		
		// 程序大循环需要k次
		for (int i = 0; i < k; i++) {
			// m指代间隔为p的两个元素前面的那个元素的索引
			int m = i;
			// n指代间隔为p的两个元素后面的那个元素的索引
			int n = (m + p) % size;
			// 用来存放临时变量值
			int temp = array[i];
			
			/*
			 * 以[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] p=6为例
			 * 则，k = 最大公约数{15, 6} = 3;
			 * 则需要三次循环， 每次循环以n和i的值相等结束
			 * 
			 * i=0: 0->6->12->3->9->0(此时n=0=i,while内循环结束)
			 * i=1: 1->7->13->4->10->1(此时n=1=i,while内循环结束)
			 * i=2: 2->8->14->5->11->2(此时n=2=i,while内循环结束)
			 * 
			 * array[i]和temp都作为临时空间存放变量
			 * 循环内做以下操作
			 * 1. 把间隔为p的两个元素中后面那个元素array[n]赋值给array[i] (此时array[i]的值已经保存在 temp中)
			 * 2. temp的值赋值给后面的元素array[n] (以此实现元素的移动)
			 * 3. array[i]的值再次赋值给temp以腾出空间被下次循环使用
			 * 4. m和n都向前移动p位，重复步骤1
			 */
			while (n != i) {
				array[i] = array[n];
				array[n] = temp;
				temp = array[i];
				m = n; n = (n + p) % size;
			}
		}

		return array;
	}

	public static void main(String[] args) {
		int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
		String str = "original array is: \n" + Arrays.toString(array)
					+ "\nthe length of array is: " + array.length + "\tthe remove step(s) is(are): 6"
					+ "\n\nafter move the array is: \n" + Arrays.toString(moveArray(array, 6));
		
		System.out.println(str);
	}
}
           

    程序运行结果如下；      original array is:      [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]     the length of array is: 15the remove step(s) is(are): 6

    after move the array is:      [9, 10, 11, 12, 13, 14, 0, 1, 2, 3, 4, 5, 6, 7, 8]

    算法时间复杂度分析：外层的for循环执行k次，针对每次for循环，内层while循环访问了整个数组的N/k，所以该算法的时间复杂度即为O(k*N/k)=O(N).符合题意要求。

    程序达到了预期效果，这说明算法基本上是正确的。回想下整个题目的解题过程，其实该题并不难，关键在于考虑问题的全面性，不能以偏概全。算法设计中要考虑问题中遇到的所有情况，提供一种通用的解决方案，或者针对每种情况分别提出相应解决方案综合在算法中，这样才能保证算法的正确性。