脚本宝典收集整理的这篇文章主要介绍了力扣 - 剑指 Offer 66. 构建乘积数组，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

剑指 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))

脚本宝典总结

以上是脚本宝典为你收集整理的力扣 - 剑指 Offer 66. 构建乘积数组全部内容，希望文章能够帮你解决力扣 - 剑指 Offer 66. 构建乘积数组所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。