51. 构建乘积数组 题目描述 给定一个数组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: 遍历数组,时间复杂度o(n) 思路2: bi a0 a1 a2 ... an-2 an-1 b0 1 a1 a2 ... an-2 an-1 b1 a0 1 a2 ... an-2 an-1 b2 a0 a1 1 ... an-2 an-1 b0 ... ... ... ... ... ... bn-2 a0 a1 a2 ... 1 an-1 bn-1 a0 a1 a2 ... an-2 1 通过观察,bi的值可以看作表格中每一行的乘积,下三角连乘易求得,上三角,从下向上也是连乘,所以我们可以先计算下三角中的连乘,再算上三角的连乘,将bi两部分相乘即可. 解答:  解法1: class sol tion { p blic: vectorint m ltiply(const vectorint& a) { int len = a.size; vectorint b; for(int i = 0; i  len; i) { int bi = 1; for(int j = 0; j  len; j) { if(i == j) contin e; bi *= a[j]; } b.p sh_back(bi); } ret rn b; } };  解法2: class sol tion { p blic: vectorint m ltiply(const vectorint& a) { int len = a.size; vectorint b(len); if(len = 0) ret rn b; b[0] = 1;  计算下三角 for(int i = 1; i  len; i) { b[i] = b[i-1] * a[i-1]; } int tmp = 1; 计算上三角 for(int i = len - 2; i = 0; --i) { tmp *= a[i+1]; b[i] *= tmp; } ret rn b; } }; 大家有兴趣可以访问我的个人博客,不定时更新一些内容哦!