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的数组,又要再分两种情况:
    1. 长度大于2且只含有一个0,例如[9 0 3]这样的数组,我们发现只需要把0所在的位置赋值为其他元素的乘积,而其他位置依然为0,返回即可。
    2. 长度大于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;
    }
};

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017