1. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

  1. 示例:
  3. 输入: [1,2,3,4,5]
  4. 输出: [120,60,40,30,24]

思路：

  • 数组B每个元素对应数组A中相同位置的元素除外的所有元素的乘积
  • 通过上述表述可以直接将数组A中的所有元素的乘积计算出来total
  • 然后遍历数组A添加数组B装配元素（每次用total/A[i]即得数组B中对应位置元素）

  • 但是题目要求不能使用除法。

    优秀解法：image.png

  • 可以在一次数组A的遍历中将绿色的下三角区域求取出来，按照规律依次乘，并利用上一次的乘积结果。

  • 然后第二次遍历用第一次遍历得到的数组B结果与对应的上三角区域的数组A中的指定值进行乘积，可得到结果。
    class Solution {
  public int[] constructArr(int[] a) {
      int length = a.length;
      if(length == 0){
          return new int[]{};
      }
      int[] res = new int[length];
      int tmp = 1;
      res[0] = 1;
      // 求下三角
      for(int i=1;i<length;i++){
          res[i] = res[i-1] * a[i-1];
      }
      // 求上三角并综合
      for(int j=length-2;j>=0;j--){
          tmp *= a[j+1];
          res[j] *= tmp;
      }
      return res;
  }
}