leetCode(43):Product of Array Except Self 分类： leetCode 2015-07-19 19:02 60人阅读 评论(0) 收藏

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.)

要考虑数组中0的个数，没有零，有一个0和有两个0的情况是不同的，如下:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int product=1;
        int nums_zero=0;
        int one_zero_pos=0;
        vector<int> output;
        for(int i=0;i<nums.size();++i)
        {
            if(nums[i]==0 && nums_zero==0)
            {
                nums_zero++;
                one_zero_pos=i;
                continue;
            }
            else if(nums[i]==0 && nums_zero==1)
            {
                nums_zero++;
                break;
            }
            product=product*nums[i];
        }
        if(nums_zero==0)
        {//没有0
             for(int i=0;i<nums.size();++i)
             {//所有数的乘积除以该数
                output.push_back(product/nums[i]);
             }
        }
        else if(nums_zero==1)
        {
             for(int i=0;i<nums.size();++i)
             {//除了为0的位置的值不为0外，其他位置都是0
                 if(i!=one_zero_pos)
                    output.push_back(0);
                 else
                    output.push_back(product);
             }
        }
        else
        {
             for(int i=0;i<nums.size();++i)
             {//全是0
                 output.push_back(0);
             }
        }
      
        return output;
    }
};