分拆數組技巧應用

分拆數組技巧應用

給你一個數組A[1..n]，請你在O(n)的時間裡構造一個新的數組B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法運算。

思路1：題目中說明，不能用除法，那一定是在相乘的時候，省略那一項，然後時間復雜度要0（n），就不能兩層循環，而是要利用前面的相乘信息來降低復雜度。

算法：相似的分拆技術在數組題中。線性時間構造兩個新數組，從開始遍歷相乘 T1[0] =1,T1[i]=T[i-1]*A[i-1] ;而 T2從後往前遍歷相乘 T2[len-1] =1，T2[i] = T2[i+1]*A[i+1] ，這樣B[i] = T1[i]*T2[i]

思路2：不能用除法，可以想到，用對數將乘法，轉為減少，這種方法理論上可行正確，但是求log出來在計算機上有誤差，不能得到精確小數。

以下是實現C++代碼實現的兩種思路：

//思路1
void special_mult1(int *A,int *B,int len)
{
    int i;
    int *T1 = new int[len];
    T1[0] = 1;
    for(i=1;i=0;i--) //從後往前累乘
        B[i] = B[i+1]*A[i+1];
    
    for(i =0;i
//思路2
void special_mult2(int *A,int *B,int len)
{
    int i;
    long long mut_result =1 ;
    for(i =0;i

例子：int A[5]={1,2,3,4,5};



可以看到，方法2計算的結果存在誤差，是不正確的。