剑指offer 74- 构建乘积数组

作者: 顾子豪 | 来源:发表于2021-06-10 01:47 被阅读0次

剑指offer 74- 构建乘积数组
[剑指offer] 构建乘积数组
【剑指 offer】构建乘积数组。
剑指offer第二版-66.构建乘积数组
【剑指Offer】051——构建乘积数组（数组）
[剑指offer][Java]构建乘积数组
【python】剑指offer，构建乘积数组？
剑指offer_构建乘积数组
剑指 offer：51、构建乘积数组
剑指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]

思考题：
能不能只使用常数空间？（除了输出的数组之外）

分析：
可以分两部分来算
$B1 =A[0]*A[1]*…*A[i-1], left[i]=A[i-1]$
$B2 *= A[i+1]*A[i+2]*…*A[n-1]$

时间复杂度： $O(n)$

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        if(A.empty()) return {};
        int n = A.size();
        vector<int> B(n);
        for(int i=0, p = 1; i<n; i++) B[i] = p, p*=A[i];
        for(int i=n-1, p = 1; i>=0; i--) B[i] *= p, p *= A[i];
        return B;
    }
};

剑指offer 74- 构建乘积数组
给定一个数组，请构建一个数组，其中中的元素。不能使用除法。样例思考题：能不能只使用常数空间？（除了输出的数组...
[剑指offer] 构建乘积数组
本文首发于我的个人博客：尾尾部落题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,....
【剑指 offer】构建乘积数组。
1、题目描述给定一个数组A[0, 1, …, n-1]，请构建一个数组B[0, 1, …, n-1]，其中B中的...
剑指offer第二版-66.构建乘积数组
本系列导航：剑指offer（第二版）java实现导航帖面试题66：构建乘积数组题目要求：给定数组A[0,1.....
【剑指Offer】051——构建乘积数组（数组）
题目描述给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A...
[剑指offer][Java]构建乘积数组
题目给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]...
【python】剑指offer，构建乘积数组？
题目：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]...
剑指offer_构建乘积数组
题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[...
剑指 offer：51、构建乘积数组
51. 构建乘积数组题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1...
剑指offer-构建乘积数组
感觉后面这几道题都是靠一些技巧，巧妙的方法解答的。这道题不能用除法自己的解法，超时了，唉看到题解用了上下三角...