【细节】剑指offer——面试题52：构建乘积数组

直接看下面的solution2，书中p263-264说明挺好a
力扣无原题，参见牛客网

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def multiply(self , A: List[int]) -> List[int]:
        # write code here
        n, temp = len(A), 1
        b = [1] * n
        for i in range(1, n): # 下三角
            b[i] = b[i-1] * A[i-1]
        for i in range(n-2, -1, -1):
            temp *= A[i+1]
            b[i] = b[i] * temp

        return b

Solution1:

自己想出来的笨蛋算法！

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        for(int i = 0; i < A.size(); i++){
            B.push_back(my_multiply(A, i));
        }
        return B;
    }
    
    int my_multiply(const vector<int>& A, int k) {
        int result = 1;
        for(int i = 0; i < A.size(); i++) {
            if(i == k) ;
            else 
                result *= A[i];
        }
        return result;
    }
};

##Solution2:
参考网址：https://www.nowcoder.com/profile/1878117/codeBookDetail?submissionId=13951708

认真捋一捋，确实快不少~~~

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size(), temp = 1;
        vector<int> B(n, 1);
        if(n > 0) {
            //计算下三角连乘
            for(int j = 1; j < n; j++) {
                B[j] = B[j-1] * A[j-1];
            }
            for(int k = n-2; k >= 0; k--) {
                temp = temp * A[k+1];
                B[k] = B[k] * temp;
            }
        }
        return B;
    }
};