238.Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
题目看起来很简单，但毕竟是一道medium的题，所以并不会像我们想的那么简单，我们首先粗略地考虑一般的情况:
- 既然要算出某一元素以外其他元素的乘积，那么我们可以先算出所有元素的乘积，最后再除以不需要的元素即可
然而如果中间某个元素值为0呢？0做除数会引发异常，所以我们需要对Corner case进行讨论
- 对于[0,1]这样的只有两个元素且其中一个元素的值为0的数组，我们发现只要交换一下两个元素然后返回即可。
修改之后，提交代码，发现自己对Corner case的讨论还不够完整，于是继续考虑。
- 对于长度大于2的数组，又要再分两种情况：
- 长度大于2且只含有一个0，例如[9 0 3]这样的数组，我们发现只需要把0所在的位置赋值为其他元素的乘积，而其他位置依然为0，返回即可。
- 长度大于2但含有不止一个0，例如[9 0 0 3]这样的数组，我们容易证明对于这样的数组，要返回的数组的所有元素应该都为0。
Corner case讨论完毕，下面我们看代码:
/*solution1 60ms*/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int i=0,res=1,count=0,zero_pos=0;
vector<int> output(nums.size(),0);
for(i=0;i<nums.size();i++)
res=res*nums[i];
if(!res){
if(nums.size()==2){
swap(nums[0],nums[1]);
return nums;
}
else if(nums.size()>2){
res=1;
/*计算除0以外所有元素的乘积，并记录0的个数和位置*/
for(i=0;i<nums.size();i++){
if(nums[i]==0){
count++;
zero_pos=i;
continue;
}
res=res*nums[i];
}
if(count==1){
output[zero_pos]=res;
return output;
}
if(count>1)
return output;
}
}
for(i=0;i<nums.size();i++)
output[i]=res/nums[i];
return output;
}
};
在参阅了讨论区之后，发现之前对题意的理解上有一点偏差。提示中说”without division”，我理解成了“不能对数组进行分割”，但这道题想表达的意思可能是“不能用除法”，所以上面的解法可能不够完美。
于是转换思路，假如有一个数组为[a,b,c,d],那么在经过这样一轮运算后得到的结果就是[bcd,acd,abd,abc],所以我们可以构造这样两个数组[1,a,ab,abc]和[bcd,cd,d,1].这样两个数组对应项相乘就可以得到结果。代码如下:
/*solution2 60ms*/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> arr1(nums.size(),1);
vector<int> arr2(nums.size(),1);
for(int i=1;i<arr1.size();i++)
arr1[i]=arr1[i-1]*nums[i-1];
for(int i=arr2.size()-2;i>=0;i--)
arr2[i]=arr2[i+1]*nums[i+1];
for(int i=0;i<arr1.size();i++)
arr1[i]=arr1[i]*arr2[i];
return arr1;
}
};
但是题目要求除了output这个要返回的数组外，空间复杂度必须为O(1)，所以我们不能开两个数组，必须采用滚动计算的方法来替换其中的一个数组。代码如下:
/*solution3 60ms*/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> arr1(nums.size(),1);
int tmp=1;
for(int i=1;i<arr1.size();i++)
arr1[i]=arr1[i-1]*nums[i-1];
for(int i=nums.size()-1;i>=0;i--){
arr1[i]=arr1[i]*tmp;
tmp=tmp*nums[i];
}
return arr1;
}
};