剑指offer—构建乘积数组 解答

剑指offer—构建乘积数组

题目描述

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

思路

如果我们使用一般的双重循环每个数进行计算,那么时间复杂度将会达到n的平方,我们需要将其优化到O(N)内

  • 使用一个数组保存每个数后面的数的乘积,通过从后向前循环累乘法保存
  • 再使用一个数组保存每个数前面的数的乘积,通过从前往后累乘法
  • 结果就是两个数组每一位对位相乘

优化:

第二步累乘计算前面的数的乘积时,我们可以在该数组的基础上直接乘,而不需要重新创建一个数组,只需要用一个变量接收累乘的结果,每一次把它乘到数组对应的位置上就可以了

问题:

  1. 第一步计算后面数乘积时,最后一个数后面没有数,乘积为0怎么办?

    循环时进行判断,如果为最后一位,就把乘积设置为1;或者进行初始化为1,而不进行该位的计算

  2. 第二步计算前面数乘积时,第一个数前面没有数怎么办?

    循环时进行判断,如果为第一位,就把乘积设置为1,或者进行初始化时设置为1,跳过第一位的判断

代码

public class Solution {
    public int[] multiply(int[] A) {
        int re = 1;
        int []dp = new int[A.length];
        int count = 0;
        for(int i=A.length-1;i>=0;i--){
            int c = i==A.length-1?1:A[i+1];
            dp[i] = i==A.length-1?1:c*count;
            count = dp[i];
        }
        for(int i=0;i<A.length;i++){
            re *= i==0?1:A[i-1];
            dp[i] *= re;
        }
        return dp;
    }
}
  • 优化代码

上面的代码很不好看,每一次循环都要判断是否为第一次循环,明显只有一次符合要求,我们考虑将它初始化

第一步计算数组每个数后面乘积时不用计算最后一个数,他后面没有数,乘积默认为1;

把A.length全部换成一个长度变量

第二 步累乘计算元素前面数的乘积时,第一个数前面没有数,不用计算,默认为1;

public class Solution {
    public int[] multiply(int[] A) {
        int re = 1,c = 0,count = 1,l = A.length;
        int []dp = new int[A.length];
        if(l<=0) return dp;
        dp[l-1] = 1;
        for(int i=l-2;i>=0;i--){
            c = A[i+1];
            dp[i] = c*count;
            count = dp[i];
        }
        for(int i=1;i<l;i++){
            re *= A[i-1];
            dp[i] *= re;
        }
        return dp;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/mul-array-build.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!