首页 > itarticle > 【算法日记69】构建乘积数组

【算法日记69】构建乘积数组

admin 11月 11, 2020 0

•

题目描述

给定一个数组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想象成一个二维矩阵，其中对角线为1，B[i]的值即为第i行的乘积。

可以把该二维矩阵以对角线分割成两部分。第一部分是一个自上而下的乘积过程，即B[i] = B[i-1] * A[i-1]，第二部分是一个自下而上的过程，即B[i] = B[i+1] *A[i+1]，将两部分相乘即可得到B[i]的值。

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public int[] multiply(int[] A) {
        if (A == null || A.length == 0)
            return null;
        int length = A.length;
        int [] B = new int[length];
        Arrays.fill(B,1);  // 将B填充1，便于后面计算
        
        int temp1 = 1;  // 计算第一部分
        for (int i=1;i<length;i++) {
            temp1 *= A[i-1];
            B[i] *= temp1;
        }
          
        int temp2 = 1;  // 计算第二部分
        for (int i=length-2;i>=0;i--) {
            temp2 *= A[i+1];
            B[i] *= temp2;
        }
        return B;
    }
}