[Jianzhi offer] 66 Build product array

The finger of the sword Offer 66. Building a product array

subject

  Given an array A[0,1,…,n-1], Please build an array B[0,1,…,n-1], among  B[i] Is the value of an array A In addition to subscript i The product of other elements , namely  B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]. Division cannot be used .

Ideas

https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/

• Initializing an array is the same as the original array ,b[0] = 1, Declare an auxiliary variable tmp = 1
• Calculation b[i] The product of the elements of the lower triangle of , Multiply directly into b[i]
• Calculation b[i] The product of the elements of the upper triangle of , Write it down as tmp, And multiply in b[i]
• return b

Code

class Solution {
    
public:
    vector<int> constructArr(vector<int>& a) {
    
        int length = a.size();
        if(length == 0)
        {
    
            return {
    };
        }
        vector<int> b(length,1); //  Declare a length of length Vector   The initial value is zero 1
        b[0] = 1;
        int tmp  = 1;

        //  Calculate the lower triangular matrix from top to bottom 
        // 
        for(int i = 1; i < length; i++)
        {
    
            b[i] = b[i - 1] * a[i - 1];
        }

        for(int i = length -2; i >= 0; i--)
        {
    
            tmp *= a[i + 1];//  You must declare a temporary variable to store   Can not be  b[i] *= a[i+1] 
            b[i] *= tmp;
        }
        return b;
    }
};