數組分拆技巧：O(n) 構造乘積數組 (不使用除法)

問題描述

給定數組 A[1..n]，構造 B[1..n] 使得 B[i] = ∏_j≠i A[j]。要求 O(n) 時間，不能使用除法。

方法一：前後綴乘積分解 (標準解法)

定義：

• `L[i] = A[0] * A[1] * ... * A[i-1]` (i 左側乘積)，`L[0] = 1`
• `R[i] = A[i+1] * ... * A[n-1]` (i 右側乘積)，`R[n-1] = 1`

則 `B[i] = L[i] * R[i]`。
可優化空間：用 B 數組直接存 L，再用一個變量累積 R 從右向左更新 B。

代碼實現 (C++)

void productExceptSelf(int* A, int* B, int n) {
    // 第一遍：B 存儲左側乘積 L
    B[0] = 1;
    for (int i = 1; i < n; i++) B[i] = B[i-1] * A[i-1];
    
    // 第二遍：從右向左累積右側乘積 R，直接乘到 B
    int R = 1;
    for (int i = n-1; i >= 0; i--) {
        B[i] *= R;
        R *= A[i];
    }
}

方法二：對數轉加法 (理論可行但有精度問題)

利用 `log(a*b) = log a + log b`，將乘法轉為加法。但浮點數精度誤差導致結果不準確，不推薦用於精確計算。

示例驗證

A = [1, 2, 3, 4, 5]

• L = [1, 1, 2, 6, 24]
• R 累積過程：1 → 5 → 20 → 60 → 120
• B = [120, 60, 40, 30, 24] ✓

複雜度

• 時間：O(n)，兩次遍歷。
• 空間：O(1) 額外空間 (輸出數組不計入)。