試分析如何把數組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).符合題意要求。

    程式達到了預期效果，這說明算法基本上是正确的。回想下整個題目的解題過程，其實該題并不難，關鍵在于考慮問題的全面性，不能以偏概全。算法設計中要考慮問題中遇到的所有情況，提供一種通用的解決方案，或者針對每種情況分别提出相應解決方案綜合在算法中，這樣才能保證算法的正确性。