题目描述
给定一个数组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 减少溢出风险
- 顺序逐个求累积，最后一个不要乘，这样每一个累积都少一个数
- 倒序逐个求累积，逐个乘以逆序累积，少一位
思路1
- 顺序逐个求累积，每个都乘，求总乘积
- 逐个除去当前的元素，剩下的每个元素就是B数组的元素
原始： 2 3 4 5 6
顺序： 1 2 6 24 120
逆序： 360 120 30 6 1
B: 360 240 180 144 120
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> vec;
int sz=A.size();
// 异常处理
if(sz==0)
return vec;
vec.push_back(1);
// 顺序累计求乘积，少一个元素
for(int i=0;i<sz-1;i++)
vec.push_back(vec.back()*A[i]);
// 倒序累计求乘积
int tmp=1;
for(int i=sz-1;i>=0;i--)
{
vec[i]=vec[i]*tmp;//少一个元素
tmp=tmp*A[i];
}
return vec;
}
};
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
