剑指OfferJZ51：构建乘积数组-java版

超、凢脫俗 2022-08-29 13:52 139阅读 0赞

### 剑指OfferJZ51：构建乘积数组-java版 ###

*   *   *   *  JZ51：给定一个数组A\[0,1,...,n-1\],请构建一个数组B\[0,1,...,n-1\],其中B中的元素B\[i\]=A\[0\]\*A\[1\]\*...\*A\[i-1\]\*A\[i+1\]\*...\*A\[n-1\]。不能使用除法。（注意：规定B\[0\] = A\[1\] \* A\[2\] \* ... \* A\[n-1\]，B\[n-1\] = A\[0\] \* A\[1\] \* ... \* A\[n-2\];）对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在

#### JZ51：给定一个数组A\[0,1,…,n-1\],请构建一个数组B\[0,1,…,n-1\],其中B中的元素B\[i\]=A\[0\]*A\[1\]*…\*A\[i-1\]*A\[i+1\]*…\*A\[n-1\]。不能使用除法。（注意：规定B\[0\] = A\[1\] \* A\[2\] \* … \* A\[n-1\]，B\[n-1\] = A\[0\] \* A\[1\] \* … \* A\[n-2\];）对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在 ####

题意为 B\[i\]=除去A数组的第i个位置的元素A\[i\],其他位置的数字相乘即可  
即为：B\[i\]=A\[0\]*A\[1\]*…A\[i-1\]\*A\[i+1\]…A\[n-1\]  
不能使用除法即为：不能使用 (A\[0\]\*A\[1\]…\*A\[n-1\]) / A\[i\] 算出B\[i\]

那么我们把 A\[0\]*A\[1\]*…A\[i-1\]\*A\[i+1\]…A\[n-1\] **分成两段**来算  
分别是  
**A\[0\]*A\[1\]*…A\[i-1\]  
和A\[i+1\]…A\[n-1\]**  
这两段数都是连续的，我们就可以采用**前缀和** 和 **后缀和**求出前段数字乘积和后段数字乘积的乘积

**前缀**：假设我们有一个字符串ABCD，A、AB、ABC、ABCD 都是这个单词的前缀  
**后缀**：D、DC、DCB、DCBA 都是这个单词的后缀

public class jz51{ 
        public int[] multiply(int[] A) { 
            int[] f1=new int[A.length];//0到i-1的乘积
            int[] f2=new int[A.length];//i+1到n-1的乘积
    
            int ans1=1;//0到i-1的乘积
            int ans2=1;//i+1到n-1的乘积
            for(int i=0,j=A.length-1;i<A.length;i++,j--){ 
                f1[i]=ans1
                ans1*=A[i];// A[0]*A[1]*...A[i-1]
    
                f2[j]=ans2;
                ans2*=A[j];//A[i+1]...A[n-1]
            }
            int[] B=new int[A.length];
            for(int i=0;i<A.length;i++){ 
                B[i]=f1[i]*f2[i];//B[i]=A[0]*A[1]*...A[i-1]*A[i+1]...A[n-1]
            }
            return B;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210720094750773.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20220829/026e9041aaec434ca6bfd8cb671fbfdf.png
[20210720094750773.gif_pic_center]: /images/20220829/b7ad40651dd84b33b930500eb1fd255b.png