[剑指 Offer 66] 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示：

• 所有元素乘积之和不会溢出 32 位整数
• a.length <= 100000

Discussion | Solution

1、不能用除法：当ans[i] = 左边数值之积 * 右边数值之积；分为两个数组 list、rlist。

2、list : list[i] 为前 i 个数值之积

     rlist: rlist[j] 为后 j 个数值之积

// @lc code=start
class Solution {
public:
    vector constructArr(vector& a) {
        if(!a.size()) return a;

        vector ans(a.size());
        vector list(a.size());
        vector rlist(a.size());

        //计算 list 和 rlist
        for(int i=0, j = a.size()-1; i <= a.size()-1; i++, j--){
            if(i == 0){
                list[i] = a[i];
                rlist[j] = a[j];
            }else{
                list[i] = a[i] * list[i-1];
                rlist[j] = a[j] * rlist[j+1];
            }
        }

        //计算 ans
        for(int i=0; i <= a.size()-1; i++){
            if(i == 0)
                ans[i] = rlist[i+1];
            else if(i == a.size()-1)
                ans[i] = list[i-1];
            else {
                ans[i] = list[i-1] * rlist[i+1];
            }
        }
        return ans;
    }
};
// @lc code=end

• 44/44 cases passed (20 ms)
• Your runtime beats 57.7 % of cpp submissions
• Your memory usage beats 13.94 % of cpp submissions (24.8 MB)

       优化思路：将ans 数组当做 list 数组， 然后从后往前计算 ans[j] = ans[j-1] * R，R为右边连乘的值。

// @lc code=start
class Solution {
public:
    vector constructArr(vector& a) {
        if(!a.size()) return a;

        vector ans(a.size());
    
        //计算 ans[i] 前 i 项数值之积
        for(int i=0 ; i <= a.size()-1; i++){
            ans[i] = i == 0 ?  a[i] : a[i] * ans[i-1];
        }

        //计算 右半部分的积
        for(int i = a.size()-1, R = 1; i >= 0; i--){
            if(i == a.size()-1){
                ans[i] = ans[i-1];
            }else if(i == 0){
                ans[i] = R * a[i+1];
            } else {
                R = R * a[i+1];
                ans[i] = ans[i-1] * R;
            }
        }
        return ans;
    }
};
// @lc code=end

• 44/44 cases passed (16 ms)
• Your runtime beats 86 % of cpp submissions
• Your memory usage beats 95.54 % of cpp submissions (23.6 MB)