剑指offer 构建乘积数组
程序员文章站
2024-03-15 12:45:05
...
1.题目
给定一个数组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]
。不能使用除法。
2.我的题解
2.1 暴力法
- 空间复杂度:
O(n^2)
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B(A.size(),1);
for(int i=0;i<A.size();i++){
for(int j=0;j<A.size();j++)
if(j!=i)B[i]*=A[j];
}
return B;
}
};
3.别人的题解
3.1 分解法
- 将B[i]分解为两部分,用上三角、下三角矩阵表示更清晰;
- 分别计算上三角部分和下三角部分,可以得到结果;
- 空间复杂度:
O(n)
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B(A.size(),1);
for(int i=1;i<A.size();i++)
B[i]=B[i-1]*A[i-1];
int temp=1;
for(int i=A.size()-2;i>=0;i--){
temp*=A[i+1];
B[i]*=temp;
}
return B;
}
};
4.总结与反思
(1)上三角矩阵与下三角矩阵;
上一篇: js数组几种常见的操作方法攻略
下一篇: C语言数组