剑指offer第五十一题。

题目描述

给定一个数组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]。不能使用除法。

解题思路

image

我们注意到，要计算B2，那么分为两个部分，左边是(A0 * A1)，右边是(An-1 * … * A3).所以对于每一个B，我们都分为两个部分进行计算即可。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        //构建与A一样长的数组B
        int len  = A.length;
        int[] B = new int[len];
        if(len != 0){
            B[0] = 1;
            //先计算左边
            for(int i=1;i<len;i++){
                B[i] = B[i-1] * A[i-1];
            }
            //再计算右边
            int tmp = 1;
            for(int i=len-2;i>=0;i--){
                tmp *= A[i+1];
                B[i] *= tmp;
            }
        }
        return B;
    }
}