首页 > 编程语言 > 详细

剑指offer:构建乘积数组

时间:2019-06-18 23:35:58      阅读:124      评论:0      收藏:0      [点我收藏+]

题目描述:

给定一个数组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]。不能使用除法。

 

思路分析:

思路一:由于不能使用除法,首先想到的就是对于A中每个元素用遍历的方式,去判断是否要乘到B数组的对应位置,这样的时间复杂度为O(n^2),超时。

思路二:用空间换时间,将B的构造分为两段,第一段为0到i-1,第二段为i+1到n,那么在构造第一段时,从前往后构造,B[i]=B[i-1]*A[i-1];构造第二段时,从后往前构造,B[i]=B[i+1]*A[i+1]。最后将两段乘起来,即为最终所求的数组。

 

代码:

 1 class Solution {
 2 public:
 3     vector<int> multiply(const vector<int>& A) {
 4         int len = A.size();
 5         if(len<=0)
 6             return A;
 7         vector<int> B(len, 1);
 8         vector<int> tmp(len, 1);
 9         for(int i=1; i<len; i++)
10             B[i] = B[i-1]*A[i-1];
11         for(int i=len-2; i>=0; i--)
12             tmp[i] = tmp[i+1]*A[i+1];
13         for(int i=0; i<len; i++)
14             B[i] = B[i]*tmp[i];
15         return B;
16     }
17 };

 

剑指offer:构建乘积数组

原文:https://www.cnblogs.com/LJ-LJ/p/11048413.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!