線性時間的棘手的部分產品

Question

給定的是包含N個數字的數組，A[0], A[1], ... A[N-1]。計算的長度N的陣列B，使得

B[i] = A[0]*A[1]*...A[i-1]*A[i+1]...*A[N-1]. 

算法應該在時間工作O(N),存儲器O(1)而不能使用劃分。

我試着通過計算前幾個項，然後以某種方式組合它們以獲得後續產品的時間。但我無法將它們結合起來。任何幫助，將不勝感激。

Answer 1

兩次遍歷數組。首先從左到右，隨時計算部分產品並將它們存儲到B中。在C狀僞代碼：

prod = 1; 
for (n=0; n<N, n++) { 
    B[n] = prod; 
    prod *= A[n]; 
} 

接着，扭轉，經歷的陣列從右到左，計算部分積並將其與值B已經乘以：

prod = 1; 
for (n=N-1; n>=0; n--) { 
    B[n] *= prod; 
    prod *= A[n]; 
}