题目

剑指 Offer 66. 构建乘积数组

思路1

• 按照一般的思路就是将所有的相乘，然后除以每一位数字就是答案，但是题目要求我们不能使用除法，因此我们会想到每次遍历到每个数字的时候，在遍历一遍数组，将除开自己以外的数字相乘，但是这样做的时间复杂度确是\(O(N^2)\)，导致超时，因此我们需要想另外一种方法来解决

• 根据题意，我们可以知道B[i]=A[0]*A[1]*A[2]*...*A[i-1]*A[i+1]*...*A[n-1]，所以我们以i为分界线，将这个拆成两部分，所以B[i]就等于A[0]*...*A[i-1]与A[i+1]*...*A[n-1]的乘积，所以数组B可以看作用一个矩阵来创建。我们以[1, 2, 3, 4]为例，如图所示：

  

  可以看出，对角线是都为1。然后从第二行开始，我们先计算下三角的每一行的乘积：B[i] = B[i-1] * A[i-1]

  从倒数第二行开始，再从下往上计算上结果：B[i] *= A[i+1]，因为左边部分已经计算出来了，所以直接拿来乘就可以了

代码

class Solution {
    public int[] constructArr(int[] a) {
        int length = a.length;

        if (length == 0) {
            return new int[0];
        }
        int[] arr = new int[length];

        // 先构建左下三角形
        arr[0] = 1;
        for (int i = 1; i < length; i++) {
            arr[i] = arr[i-1] * a[i-1];
        }
        // 构建右上三角形同时计算结果
        int temp = 1;
        // 从倒数第二个开始往前
        for (int i = length-2; i >= 0; i--) {
            temp *= a[i+1];
            arr[i] *= temp;
        }

        return arr;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(1)\)