您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

《編程珠玑》雜技法：數組循環左移 O(1) 空間原地算法完整證明與實現

編輯：關於C語言

問題描述

長度為 L 的數組，將前 N 個元素**循環左移**到末尾。要求：**O(1) 額外空間、O(L) 時間、原地修改**。

例：[1,2,3,4,5,6], N=2 → [3,4,5,6,1,2]

雜技法核心思想

將數組視為**首尾相連的環**。從位置 i 出發，反覆跳躍 N 步：i → i+N → i+2N → ... (模 L)，直到回到起點。這構成一個**環**。

設 d = gcd(L, N)（最大公約數），則數組分解為 **d 個互不相交的環**，每環長度 L/d。依次處理每個環，完成整體循環移位。

數學證明：為什麼正確？

引理 1：每個環長度 = L / d

設 L = α·d, N = β·d，gcd(α, β) = 1。
環中位置滿足 i + k·N ≡ i (mod L) ⇔ k·β·d ≡ 0 (mod α·d) ⇔ k·β ≡ 0 (mod α)。
因 gcd(α,β)=1，最小正整數解 k = α。故環長度 = α = L/d。

引理 2：共 d 個互不相交的環

總元素 L，每環 L/d 個，故環數 = d。
環的起點為 0, 1, ..., d-1。
證明不同環無交集：若環 i 和 j (i≠j) 有公共元素，則 i + k₁N ≡ j + k₂N (mod L) ⇒ (i-j) ≡ (k₂-k₁)N (mod L)。兩邊同除 d，得 (i-j)/d ≡ (k₂-k₁)β (mod α)。但 0 < |i-j|/d < α，且 β 與 α 互質，矛盾。

引理 3：處理順序正確性

每個環內按順序「接力傳遞」元素：
temp = a[i]; a[i] = a[i+N]; a[i+N] = a[i+2N]; ... a[last] = temp
因環內無重複位置（引理 1），且環間無交集（引理 2），每個元素**恰好被讀寫一次**，最終達到整體循環左移 N 位效果。

兩種實現版本

版本一：雙層循環（教科書風格）

void juggleRotate1(int* a, int L, int N) {
    N %= L; if (N == 0) return;
    int d = std::gcd(L, N);
    for (int start = 0; start < d; ++start) {
        int temp = a[start];
        int cur = start;
        while (true) {
            int next = (cur + N) % L;
            if (next == start) break;
            a[cur] = a[next];
            cur = next;
        }
        a[cur] = temp;
    }
}

版本二：單循環 + 計數器（更緊湊）

void juggleRotate2(int* a, int L, int N) {
    N %= L; if (N == 0) return;
    int temp = a[0];
    for (int moved = 0, cur = 0, start = 0; moved < L; ++moved) {
        int next = (cur + N) % L;
        if (next == start) { // 當前環結束
            a[cur] = temp;
            ++start;
            cur = start;
            if (start < L) temp = a[start]; // 下一環
        } else {
            a[cur] = a[next];
            cur = next;
        }
    }
}

對比：三大原地旋轉算法

算法	時間	空間	原理	代碼複雜度	適用場景
雜技法	O(L)	O(1)	gcd 分解環，接力傳遞	中	嵌入式、內存極受限、教學展示數論之美
三次反轉法	O(L)	O(1)	reverse(0,N-1); reverse(N,L-1); reverse(0,L-1)	極低	工程首選、易讀、易維護、編譯器優化好
塊交換法	O(L)	O(1)	遞歸交換左右塊	高	理論研究、特定硬件優化

三次反轉法參考實現（推薦生產使用）

void reverse(int* a, int l, int r) {
    while (l < r) std::swap(a[l++], a[r--]);
}
void rotateReverse(int* a, int L, int N) {
    N %= L; if (N == 0) return;
    reverse(a, 0, N-1);
    reverse(a, N, L-1);
    reverse(a, 0, L-1);
}

C++ 標準庫：`std::rotate`

#include 
#include 

int main() {
    std::vector v = {1,2,3,4,5,6};
    std::rotate(v.begin(), v.begin() + 2, v.end()); // 左移 2
    // v = {3,4,5,6,1,2}
}

標準庫實現：通常採用**三次反轉法**或**塊交換法**的優化版，經過極致調優，**生產代碼直接用 `std::rotate`**。