PAT 1008 數組元素循環右移問題：C語言解法詳解與優化
PAT（Basic Level）1008 題目要求實現數組元素的循環右移操作。給定一個整數數組和移動位數 M，將數組中的元素向右循環移動 M 位。例如，數組 {1, 2, 3, 4, 5} 右移 2 位後變為 {4, 5, 1, 2, 3}。本文將分析兩種不同的解法，並探討如何優化時間複雜度。
題目理解與關鍵點
核心難點在於處理 M 大於數組長度 N 的情況。由於循環移動 N 位等同於不移動，因此實際有效移動位數為 M % N。若直接執行 M 次單步移動，時間複雜度為 O(M×N)，當 M 很大時會超時。優化關鍵在於先取模運算，將移動次數限制在 0 到 N-1 之間。
解法一：暴力單步移動（Ver.2 通過版）
此版本通過嵌套循環實現：外層循環 M 次，內層將數組整體右移一位。雖然邏輯直觀，但未對 M 取模，僅因測試數據較弱而通過。代碼片段如下：
int temp;
for(i=0; i=0; j--){
array[j+1] = array[j];
}
array[0] = temp;
}
缺點：若 M 遠大於 N，會產生大量無效循環，效率極低。
解法二：直接計算新位置（Ver.1 部分通過）
此版本嘗試優化：先將 M 限制在 0~N 範圍（註釋掉的 while 迴圈），再直接輸出重新排序後的元素，避免實際移動數組。但提交時若啟用取模邏輯反而報錯，原因在於 m /= n 是整除而非取模，導致 M 變為 0 或 1，邏輯錯誤。正確寫法應為 m = m % n。
優化後的標準解法
結合兩版優點，正確解法應包含：
- 讀入 N、M 及數組元素
- 計算有效移動位數：
m = m % n
- 直接按新順序輸出：先輸出後 M 個元素，再輸出前 N-M 個元素
- 注意格式控制：首個元素無前導空格，其餘前加空格
m = m % n; // 關鍵優化步驟
for(i = n - m; i < n; i++) {
if(i == n - m) printf("%d", array[i]);
else printf(" %d", array[i]);
}
for(i = 0; i < n - m; i++) {
printf(" %d", array[i]);
}
printf("\n");
常見錯誤總結
- 使用
m /= n 而非 m %= n 導致邏輯錯誤
- 未處理 M 為 0 或 M 為 N 的邊界情況
- 輸出格式不符合要求（多餘空格或換行）
- 數組越界：直接訪問
array[n-m] 時未確保 m < n
複雜度分析
優化後時間複雜度為 O(N)，空間複雜度 O(N)。僅需一次遍歷輸出，無需實際移動數組元素，是解決此類循環移位問題的標準高效做法。
