leetcode_product_of_array_except_self

发表于

难度：Medium

假如数组[1,2,3,4,5,6]
则结果：
第一位    1            *    2*3*4*5*6
第二位    1            *    3*4*5*6
第三位    1*2            *    4*5*6
第四位    1*2*3        *    5*6
第五位    1*2*3*4    *    6
第六位    1*2*3*4*5    *    1

分别从前向后、从后向前遍历，从前向后乘到上一个元素的积、从后向前乘到下一个元素的积。然后每一个元素的两个积相乘，即为解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret(nums.size(),1);
        int product = 1;
        for(int i = 0;i < nums.size();i++)
        {
            ret[i] = product;
            product *= nums[i];
        }
        product = 1;
        for(int i = nums.size()-1; i >= 0;i--)
        {
            ret[i] *= product;
            // cout<<"i:"<<i<<", result: "<<ret[i]<<endl;
            product *= nums[i];
        }
        return ret;
    }
};

46ms，82.17%