剑指offer | 面试题66：构建乘积数组

转载本文章请标明作者和出处
本文出自《Darwin的程序空间》
本文题目和部分解题思路来源自《剑指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]。不能使用除法

• 示例

  输入: [1,2,3,4,5]
  输出: [120,60,40,30,24]
  

• 提示

  所有元素乘积之和不会溢出 32 位整数
  a.length <= 100000
  

解题分析

题目要求不能使用除法，所以你求出所有的数的乘积，然后再除以每个数构结果集的第一想法就流产了；

这道题就是要求结果数组上的每一个数，都是原数组除了这个位置的数的乘积；

以第二个节点为例，其实就是这个当前节点元素所有在原数组左边的元素乘积乘以原数组在这个索引右边的元素乘积；

那么我们的做法就是，先把每一个元素的左边的乘积和右边的乘积都算出来，然后新的数组的元素就等于这个元素左边的乘积加上右边的乘积；

如上图中的示例，所有左边的乘积为：

这个数组上所有的位置上的数都是原数组此位置上的书的左边的所有元素的乘积

如上图中的示例，所有右边的乘积为：

这个数组上所有的位置上的数都是原数组此位置上的书的右边的所有元素的乘积，

最后所求数组即使这两个数据的相同位置索引的乘积构成的新数组；

然后我们使用累乘，少定义两个数组即可完成最优算法；

代码

ps：这里笔者使用的jdk为1.8、Python3.7版本

• java实现

class Solution {
    public int[] constructArr(int[] a) {
        if (Objects.isNull(a) || a.length == 0) {
            return new int[]{};
        }
        int[] res = new int[a.length];
        int left = 1;
        for (int i = 0; i < res.length; i++) {
            res[i] =left;
            left *= a[i];
        }
        int right = 1;
        for (int i = res.length - 1; i >= 0; i--) {
            res[i] *= right;
            right *= a[i];
        }
        return res;
    }
}

• Python实现

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        if a is None or len(a) == 0:
            return []
        res = [None] * len(a)
        left = 1
        for i in range(len(a)):
            res[i] = left
            left *= a[i]
        right = 1
        for i in reversed(range(len(a))):
            res[i] *= right
            right *= a[i]
        return res

最后

以上就是甜美香水为你收集整理的剑指offer | 面试题66：构建乘积数组的全部内容，希望文章能够帮你解决剑指offer | 面试题66：构建乘积数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。