题解 | #构建乘积数组#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型一维数组
     * @return int整型一维数组
     */
    public int[] multiply (int[] A) {
        // write code here
        int[] mul1 = new int[A.length];
        int[] mul2 = new int[A.length];
        int mul = 1;
        //记录A[0]~A[i-1]的乘积值
        for (int i = 0; i < A.length; i++) {
            mul1[i] = mul;
            mul *= A[i];
        }
        mul = 1;
        //记录A[i+1]~A[n-1]的乘积值
        for (int i = A.length - 1; i >= 0; i--) {
            mul2[i] = mul;
            mul *= A[i];
        }
        int[] ret = new int[A.length];
        //于是ret[i]登录mul1[i]*mul2[i]
        for (int i = 0; i < A.length; i++) {
            ret[i] = mul1[i] * mul2[i];
        }
        return ret;
    }
}

一个比暴力求解好一点的方法，时间复杂度为O(n)

额外用两个数组mul1和mul2，分别记录从A[0] ~ A[i-1]和A[i+1] ~ A[n-1]的乘积值，时间复杂度为O(n)

然后B数组可以用mul1[i]*mul2[2]的方式计算，时间复杂度为O(n)

所以最终的时间复杂度为O(n)