Skip to content

Latest commit

 

History

History
16 lines (10 loc) · 639 Bytes

构建乘积数组.md

File metadata and controls

16 lines (10 loc) · 639 Bytes

构建乘积数组

知识点:

题目描述

给定一个数组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[i]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。 image-20190309104334318

代码

这里