[51] 构建乘积数组(简单)
[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]
对于 A 长度为 1 的情况,B 无意义,故而无法构建,因此该情况不会存在。
输入:[1,2,3,4,5]
返回值:[120,60,40,30,24]

解题思路

双循环遍历

其实题意就是 B[i] 等于 A 中所有除了 A[i] 的其他元素相乘。
/**
 * 双循环遍历
 * T(n^n) S(n)
 */
public static int[] multiply(int[] A) {
    int[] result = new int[A.length];
    for (int i = 0; i < result.length; i++) {
        result[i] = 1;
        for (int j = 0; j < A.length; j++) {
            if (j == i) {
                continue;
            }
            result[i] *= A[j];
        }
    }
    return result;
}