剑指offer 51.构建乘积数组

剑指offer 51.构建乘积数组

题目

给定一个数组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];）

思路

这就要从双向往中间计算，首先计算前半部分，就是第一个for循环，对于B[i]来说，这里已经乘上了前半部分，还缺A[i+1]后面的，这时候第二个循环，反向，先给A[len-1]，然后向前逼近，设置一个临时变量表示后半的A乘积。

代码

public int[] multiply(int[] A) {
  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 temp = 1;
    for (int j = len - 2; j >= 0; j--) {
      temp *= A[j + 1];
      B[j] *= temp;
    }
  }
  return B;
}