题目描述

给定一个数组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数组中所有元素相乘，使用这个乘积除以A[i]，即可得到B[i]。但由于题目限制不使用除法，另一个直观的解法是将A数组按照i的位置分为两部分，然后连乘这两部分中的所有元素即可。这里给出两种实现方法。

时间复杂度为，空间复杂度为。

下面是参考代码：

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

public int[] constructArr(int[] a) {
    int[] res = new int[a.length];
    for (int i = 0; i < a.length; i++) {
        int temp = 1;
        for (int j = 0; j < a.length; j++) {
            if (j == i) continue;
            temp *= a[j];
        }
        res[i] = temp;
    }
    return res;
}

题解二

这里是剑指中的思路，非常巧妙。

数组B可以用一个矩阵来创建，此时B[i]的值就是矩阵中每行的乘积。定义C数组保存下三角每行乘积的值，定义D数组保存上三角每行乘积的值。因此C[i] = C[i-1] * A[i-1], D[i] = D[i+1] * A[i+1]，最后再将C和D数组中的对应元素相乘得到B数组。

把数组B看成一个矩阵来创建

时间复杂度为，空间复杂度为。

下面是参考代码：

class Solution {
    public int[] constructArr(int[] A) {
        int n = A.length;
        if (n == 0)
            return new int[0];
        int[] B = new int[n], C = new int[n], D = new int[n];
        C[0] = 1; D[n-1] = 1;

        // 计算下三角
        for (int i = 1; i < n; i++)
            C[i] = C[i-1] * A[i-1];
        // 计算上三角
        for (int i = n-2; i >= 0 ; i--)
            D[i] = D[i+1] * A[i+1];
        // 计算B数组
        for (int i = 0; i < n; i++)
            B[i] = C[i] * D[i];
        return B;
    }
}