數組循環左移 P 位：三次逆置法 O(1) 空間原地算法

問題

將長度 n 數組 R 循環左移 P 位（0 < P < n），即 {X0..Xn-1} → {Xp..Xn-1, X0..Xp-1}。

三次逆置法

1. 逆置前 P 個元素：Reverse(R, 0, P-1)
2. 逆置剩餘元素：Reverse(R, P, n-1)
3. 逆置整個數組：Reverse(R, 0, n-1)

代碼實現

[c]
void Reverse(int R[], int l, int r) {
    int temp;
    for (int i = l, j = r; i < j; i++, j--) {
        temp = R[i]; R[i] = R[j]; R[j] = temp;
    }
}

void RCR(int R[], int n, int p) {
    if (p <= 0 || p >= n) { printf("ERROR\n"); return; }
    Reverse(R, 0, p-1);
    Reverse(R, p, n-1);
    Reverse(R, 0, n-1);
}

複雜度

• 時間：O(n)，每個元素移動常數次。
• 空間：O(1)，原地操作。

示例

R={1,2,3,4,5,6}, P=2 → 步驟1 {2,1,3,4,5,6} → 步驟2 {2,1,6,5,4,3} → 步驟3 {3,4,5,6,1,2} ✓