剑指Offer(五十一):构建乘积数组

  • A+
所属分类:剑指Offer
摘要

根据特定公式,计算乘积数组。

剑指Offer(五十一):构建乘积数组

一、前言

本系列文章为《剑指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、思路

观察下公式,你会发现,B[i]公式中没有A[i]项,也就是说如果可以使用除法,就可以用公式B[i]=A[0]*A[1]*.....*A[n-1]/A[i]来计算B[i],但是题目要求不能使用,因此我们只能另想办法。

现在要求不能使用除法,只能用其他方法。一个直观的解法是用连乘n-1个数字得到B[i]。显然这个方法需要O(n*n)的时间复杂度。

好在还有更高效的算法。可以把B[i]=A[0]*A[1]*.....*A[i-1]*A[i+1]*.....*A[n-1]。看成A[0]*A[1]*.....*A[i-1]和A[i+1]*.....A[n-2]*A[n-1]两部分的乘积。

即通过A[i]项将B[i]分为两部分的乘积。效果如下图所示:

剑指Offer(五十一):构建乘积数组

不妨设定C[i]=A[0]*A[1]*...*A[i-1],D[i]=A[i+1]*...*A[n-2]*A[n-1]。C[i]可以用自上而下的顺序计算出来,即C[i]=C[i-1]*A[i-1]。类似的,D[i]可以用自下而上的顺序计算出来,即D[i]=D[i+1]*A[i+1]。

如果还是不明白,没有关系,直接看下代码,细细体会下就懂了。

剑指Offer(五十一):构建乘积数组

第一个for循环用来计算上图1范围的数,第二个for循环用来计算上图2范围的数。

2、代码

C++:

Python:

python可以利用reduce方法快速求解。

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: