每日一题，提升自己。今天分享一道关于数组构建的题目，且听我细细道来。

数组 - 构建数组

1. 题目描述

    给定一个数组 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]。不能使用除法。

示例：

输入：[1,2,3,4,5]

输出：[120,60,40,30,24]

提示：

所有元素乘积之和不会溢出 32 位整数。

A.lengtn <= 100000

2. 解题思路

        这道题如果可以用除法的话，那就很简单了，先遍历数组求出所有数的乘积，然后在依次除以每个位置对应的值即可。但是现在是不让使用除法，那么最简单的思路就是将B[i]每个位置都把所有需要的数乘一遍，这样可以解决问题，但是这样的问题就是所用的时间复杂度会非常高。
        那怎么降低时间复杂度呢？方法将数组B每个位置的需要相乘的数构建成一个二维数组，然后以A[i]为界限，将其分割成左右三角形，其中每个三角形从尖部到底部都是可以累积的，这样上一次的计算结果就可以用于下一次的计算，大大减少了时间复杂度。具体见下图。

复杂度：

• 时间复杂度：O(n)。因为左右三角形遍历求乘积的时间复杂度都是O(n)。
• 空间复杂度：O(1)。不将结果数组算入的话，只需要使用常量的工作空间。

3. 算法流程

1. 首先申请结果数组res。
2. 求出左侧三角形从上到下的乘积值，并依次存入res[i]中。
3. 求出右侧三角形从下到上的乘积值，并且和之前的res[i]做乘积存入，即可得到结果数组。

计算左侧三角形

计算右侧三角形

4. 代码实现

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static int[] constructArr(int[] a){
    int[] res = new int[a.length];
    // 从上到下计算左下三角，见计算左侧三角形图
    int left = 1;
    for (int i=0; i<a.length; i++){
        res[i] = left;
        left *= a[i];
    }
    // 从下到上计算右上三角并和之前的res[i]做乘积存入，见计算右侧三角形图
    int right = 1;
    for (int i= a.length-1; i>=0; i--){
        res[i] *= right;
        right *= a[i];
    }
    return res;
}