题解 | #构建乘积数组# | 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]

已知信息

  1. 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来暴力解法

  1. 需要跳过下标 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次遍历,就可以得到 左边的值和右边的值了。

  1. 下标从0开始统计左边的值
  2. 下标从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;
    }
}

复杂度分析

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

全部评论

相关推荐

2 1 评论
分享
牛客网
牛客企业服务