题解 | JZ51-构建乘积数组

一、找规律-左右分开计算

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        if(A==null || A.length<2)
            return null;
        int[] B=new int[A.length];
        B[0]=1;
  //这一轮循环下来，B数组中暂时存放了自己对应左下三角的乘积
  //即自己分成了左右两部分相乘后，左边部分的值此时拿到了
        for(int i=1;i<A.length;i++)
            B[i]=B[i-1]*A[i-1];
        int temp=1;
        for(int i=A.length-2;i>=0;i--){
            temp*=A[i+1];
          //temp =temp*A[i+1]; temp就是i位置对应的右边部分的值 从A[n-1]一直乘到A[1]
            B[i]*=temp;
          //B[i] =B[i]*temp; 左边部分乘上右边部分
        }
        return B;
    }
}

二、双重for循环
将i位置上的数值设置成1，之后再还原
时间复杂度：O(n^2)

public int[] multiply(int[] A) {
    int[] B = new int[A.length];
    int temp = 0;
    for (int i = 0; i < A.length; i++) {
        temp = A[i];
        A[i] = 1;
        B[i] = 1;
        for (int j = 0; j < A.length; j++) {
            B[i] *= A[j];
        }
        A[i] = temp;
    }
    return B;
}