题解 | #构建乘积数组# | JAVA | 暴力 | 动态规划 |

构建乘积数组

http://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46

题目描述

给定一个数组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

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

返回值：
[120,60,40,30,24]

已知信息

A的长度是要大于1的，可以不用做非空判断

方法一: 暴力解法

思路和算法

由题意可以知道:
B[0] = A[1] * A[2] * A[3] * A[4] * .. * A[n-2] * A[n-1] 【不包含A[0]的值】
B[1] = A[0] * A[2] * A[3] * A[4] * .. * A[n-2] * A[n-1] 【不包含A[1]的值】
B[2] = A[0] * A[1] * A[3] * A[4] * .. * A[n-2] * A[n-1] 【不包含A[2]的值】
B[3] = A[0] * A[1] * A[2] * A[4] * .. * A[n-2] * A[n-1] 【不包含A[3]的值】
B[i]= A[0] * A[1] ... A[i-1] * A[i+1] ... A[n-1] 【不包含A[i]的值】
每次都要把数组A从0到n相乘并排除自身A[i]所在的值
我们可以假设 A[i] = 1 ，得到如下表格

图片说明

正常思路是什么？
我们可以将 A[0] .... A[n-1] 相乘起来，这样只需要遍历一遍A数组就可以得到总和，然后在将总和除以 A[i] ,可得到B数组
但是题目要求，不能用除法，这种不行。

由表可以看出，每次想得到 B[i] 的值，都需要遍历一次 A 数组
由题目知道： B数组长度是等于 A 数组的，所以我们可以进行双重for来暴力解法

需要跳过下标 i == j 或者 sum = sum * 1

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int n = A.length;
        int[] B = new int[n];
        for (int i = 0; i < n; i++) { //第一重for循环，遍历B[i-n]
            int sum = 1; // 用来遍历统计 B[i]= A[0] * A[1] *...* A[i-1] * A[i+1] *...* A[n-1]
            for (int j = 0; j < n; j++) { // 第二重for循环，统计B[i]的值
                if (j == i) {
                    continue;  // 遇到i==j时要跳过，或者乘1也可以
                }
                sum = sum * A[j];
            }
            B[i] = sum;
        }
        return B;
    }
}

复杂度分析

时间复杂度：O(N^2)
空间复杂度: O(1)

方法二：动态规划

由暴力解法可以知道，我们做了很多重复的操作，每一遍都重复统计了 A[0] - A[n-1] 的数据，可以利用动态规划的思想，用空间换时间的方法，把之前已经做的值用数组保存起来

图片标题

我们可以把绿色划分成左边，把红色划分成右边。计算 B[i]
B[i] = 左边绿色的数据 * 右边红色数据

计算左边：

left[0] = 1
left[1] = A[0] = left[0] * A[0]
left[2] = A[0] * A[1] = left[1] * A[1]
left[3] = A[0] * A[1] * A[2] = left[2] * A[2]
.....
left[n] = A[0] * A[1] * A[2] .. A[n-1] = left[n-1] * A[n-1]

left[n] = left[n-1] * A[n-1]

由此可知，left[n] 是由 left[n-1] 可以得出来的，这里我们用，把 left[n-1] 存起来，这样就不需要重复统计了

计算右边：

right[0] = A[1] * A[2] .. A[n-1] = A[1] * right[1]
right[1] = A[2] .. A[n-1] = A[2] * right[2]
right[2] = A[3] .. A[n-1] = A[3] * right[3]
right[3] = A[4] .. A[n-1] = A[4] * right[4]
......
right[n-2] = A[n-1] * right[n-1]
right[n-1] = 1

right[n] = A[n+1] + right[n+1]

可以发现，相比较上面的左边而言，右边的统计如果下标从0开始不太好统计，我们下标可以从 n - 1 开始统计。

这样就能知道，只需要2次遍历，就可以得到左边的值和右边的值了。

下标从0开始统计左边的值
下标从n-1开始统计右边的值

import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
        int n = A.length;
        //维护2个数组，用空间换时间
        int[] left = new int[n];
        int[] right = new int[n];
        //根据上面已经知道第0个是1
        left[0] = 1;
        //这里下标从1开始
        for (int i = 1; i < n; i++) {
            //根据计算左边得出结论。left[n] = left[n-1] * A[n-1]
            left[i] = left[i - 1] * A[i - 1];
        }
        //根据计算右边知道，第n-1个是1
        right[n - 1] = 1;
        // 这里下标从数组第2个值开始，第一个值已经是 1 了
        for (int i = n - 2; i >= 0; i--) {
            //根据计算右边得出结论。right[n] = A[n+1] + right[n+1]
            right[i] = right[i + 1] * A[i + 1];
        }

        //开始计算B数组
        int[] B = new int[n];
        for (int i = 0; i < n; i++){
            B[i] = left[i] * right[i];
        }
        return B;
    }
}

这里想对比上面暴力解法，多了 left 和 right 数组，所以额外维护了2个数组空间复杂度会提高.

空间复杂度：O(N)
时间复杂度：O(N)

进一步优化:

left 数组显然有点多余，可以直接用 B 数组临时代替 left 数组

import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
       int n = A.length;
        //维护2个数组，用空间换时间 ,这里可以用B数组代替left数组，达到节约一个额外数组
        int[] B = new int[n];
        int[] right = new int[n];
        //根据上面已经知道第0个是1
        B[0] = 1;
        //这里下标从1开始
        for (int i = 1; i < n; i++) {
            //根据计算左边得出结论。left[n] = left[n-1] * A[n-1]
            B[i] = B[i - 1] * A[i - 1];
        }
        //根据计算右边知道，第n-1个是1
        right[n - 1] = 1;
        // 这里下标从数组第2个值开始，第一个值已经是 1 了
        for (int i = n - 2; i >= 0; i--) {
            //根据计算右边得出结论。right[n] = A[n+1] + right[n+1]
            right[i] = right[i + 1] * A[i + 1];
        }

        //开始计算B数组
        for (int i = 0; i < n; i++){
            B[i] = B[i] * right[i];
        }
        return B;
    }
}

用B 数组代替 left数组后，可以节约一个数组

空间复杂度：O(N)
时间复杂度：O(N)

还能进一步优化吗？

left 数组是怎么都要计算保存的，但是right数组需要吗？ right数组可以简化，我们用 right这个变量来代替，空间复杂度又可以缩小到常数级

import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
      int n = A.length;
        //维护2个数组，用空间换时间 ,这里可以用B数组代替left数组，达到节约一个额外数组
        int[] B = new int[n];
        //根据上面已经知道第0个是1
        B[0] = 1;
        //这里下标从1开始
        for (int i = 1; i < n; i++) {
            //根据计算左边得出结论。left[n] = left[n-1] * A[n-1]
            B[i] = B[i - 1] * A[i - 1];
        }
        //根据计算右边知道，第n-1个是1
        int right = 1;

        //开始计算B数组
        for (int i = n - 2; i >= 0 ; i--){
            //根据计算右边得出结论。right[n] = A[n+1] + right[n+1]
            right = right * A[i+1];
            // B[i] = left[i] * right[i]
            B[i] = B[i] * right;
        }
        return B;
    }
}