题解 | #除自身以外数组的乘积#
除自身以外数组的乘积
http://www.nowcoder.com/practice/0786aa81c1c64c2a990e393fac811b45
题意：
方法一：
前缀积+后缀积
思路：遍历数组，分别计算前缀积和后缀积。
计算公式如下：
class Solution {
public:
int a[1000005]={1};
int b[1000005]={0};
vector<int> timesExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> res(n);
for(int i=1;i<=n;i++){
a[i]=a[i-1]*nums[i-1];
}
b[n+1]=1;
for(int i=n;i>=1;i--){
b[i]=b[i+1]*nums[i-1];
}
for(int i=1;i<=n;i++){
res[i-1]=a[i-1]*b[i+1];
}
return res;
}
};
时间复杂度：%2C%E9%81%8D%E5%8E%86%E6%95%B0%E7%BB%84%E3%80%82)
空间复杂度：%2C%E5%AD%98%E5%82%A8%E5%89%8D%E7%BC%80%E7%A7%AF%E5%92%8C%E5%90%8E%E7%BC%80%E7%A7%AF%E6%95%B0%E7%BB%84%E3%80%82)
方法二：
空间优化
思路：针对方法一的空间优化：去除前缀积数组和后缀积数组，只用必要数组res进行前缀运算和后缀运算。
class Solution {
public:
vector<int> timesExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> res(n,1);//初始化
for(int i=1;i<n;i++){//计算前缀积
res[i]=res[i-1]*nums[i-1];
}
int t=1;
for(int i=n-2;i>=0;i--){//计算后缀积
t*=nums[i+1];
res[i]*=t;
}
return res;
}
};
时间复杂度：空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
查看21道真题和解析