剑指 Offer 66. 构建乘积数组

剑指 Offer 66. 构建乘积数组

难度：$middle$

题目描述

给定一个数组 $A[0,1,\dots ,n-1]$，请构建一个数组 $B[0,1,\dots ,n-1]$，其中 $B[i]$ 的值是数组 $A$ 中除了下标 $i$ 以外的元素的积, 即 $B[i]=A[0]\times A[1]\times \dots \times A[i-1]\times A[i+1]\times \dots \times A[n-1]$。不能使用除法。

示例:

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

提示：

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

算法

(前缀和)

本题的难点在于 不能使用除法 ，即需要 只用乘法 生成数组 B 。根据题目对 B[i] 的定义，可列表格，如下图所示。

根据表格的主对角线（全为 1 ），可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果。

我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。

对于给定索引 i，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积。下面让我们更加具体的描述这个算法。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度。

• 空间复杂度 : $O(n)$，其中 $n$ 是数组的长度。

C++ 代码

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        if (a.empty()) return vector<int>();

        int n = a.size();
        vector<int> b(n, 0);

        // 左边
        for (int i = 0, p = 1; i < n; i ++) {
            b[i] = p;
            p *= a[i];
        }

        //右边
        for (int i = n - 1, p = 1; ~i; i --) {
            b[i] *= p;
            p *= a[i];
        }

        return b;

    }
};