剑指Offer（五十一）-- 构建乘积数组

秦怀杂货店

发布于 2022-02-15 14:03:27

3060

Github仓库地址：https://github.com/Damaer/CodeSolution 刷题笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

给定一个数组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,2,3,4,5]

输出

[120,60,40,30,24]

思路以及解答

由于这道题不可以使用除法，如果使用暴力做法的话，需要每一个数值，都计算其他所有数的乘积，那这样的算法时间复杂度是O(n2),空间复杂度为O(n)，显然是不符合要求的。

    public int[] multiply(int[] A) {
        if(A!=null) {
            int []nums = new int[A.length];
            for (int i = 0; i < A.length; i++) {
                int result = 1;
                for (int j = 0; j < A.length; j++) {
                    // 跳过自身
                    if (j == i)
                        continue;
                    // 其他的都乘起来
                    result *= A[j];
                }
                nums[i]= result;
            }
            return nums;
        }
        return null;
    }

再想想更优的做法，可以分解开看。最后的结果中，每一个数，都是等于它左边的所有数，乘以它右边的所有数。那么我们可以申请一个数组，假设为B[]，第一次遍历的数组A[]的时候，把每一个数A[i]左边的所有数的乘积，乘起来，放在B[i]的位置。此时，每一个数左边的乘积已经有了，如何计算右边的乘积呢？

可以同样申请一个数组C[]存起来，但是没有必要，因为我们从右边往左边遍历的时候，只需要用一个临时变量，把右边的乘积存着，和左边的乘积相乘，赋值到原来的数组A[]，就可以了。

代码如下：

    public int[] multiply(int[] A) {
        if (A == null || A.length < 2)
            return null;
        int[] B = new int[A.length];
        // 初始化第一个值
        B[0] = 1;
        // 计算左边的乘积
        for (int i = 1; i < A.length; i++)
            B[i] = B[i - 1] * A[i - 1];
        // 初始化临时变量
        int temp = 1;
        // 从右边往左边计算
        for (int i = A.length - 2; i >= 0; i--) {
            // 计算右边的乘积
            temp *= A[i + 1];
            // 右边乘以左边
            B[i] *= temp;
        }
        return B;
    }

上面的做法相当于申请了大小为n的临时空间，空间复杂度为O(n)，遍历了数组两遍，时间复杂度为O(2n)，也就是O(n)。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-08，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法