數組循環左移P位：三次逆置法的O(1)空間實現

問題定義

將長度為n的數組R循環左移P位（0<P<n），即{X₀,X₁,...,Xₙ₋₁} → {Xₚ,Xₚ₊₁,...,Xₙ₋₁,X₀,X₁,...,Xₚ₋₁}。

三次逆置算法原理

利用逆序操作的結合性，分三步完成：

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

完整代碼實現

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

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

算法優勢分析

實戰注意事項

• 參數校驗：確保0 < p < n
• 邊界處理：p=0或p=n時數組不變
• 類型泛化：用void*+元素大小可實現泛型版本