剑指offer(C++)-JZ66：构建乘积数组(算法-其他)-CSDN博客

作者翟天保Steven
版权声明著作权归作者所有商业转载请联系作者获得授权非商业转载请注明出处

题目描述

给定一个数组 A[0,1,...,n-1] ,请构建一个数组 B[0,1,...,n-1] ,其中 B 的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]除 A[i] 以外的全部元素的的乘积。程序中不能使用除法。注意规定 B[0] = A[1] * A[2] * ... * A[n-1]B[n-1] = A[0] * A[1] * ... * A[n-2]

对于 A 长度为 1 的情况B 无意义故而无法构建用例中不包括这种情况。

数据范围1≤n≤10  数组中元素满足∣val∣≤10

示例

输入

[1,2,3,4,5]

返回值

[120,60,40,30,24]

解题思路

本题考察算法思维。如下图所示已知A求B。解题思路如下

1. B[n]=除了A[n]之外所有A乘积那么基于下表可以将B的乘积序列以n为分界线分为前后两部分。
2. 先累积n之前的A顺序执行B[n]=B[n-1]*A[n-1]。
3. 再累积n之后的A倒序执行B[n]=B[n]*temp其中temp从1开始累积A即temp=1*A[n-1]*A[n-2].......*A[1]。

测试代码

class Solution {
public:
    // 乘积
    vector<int> multiply(vector<int>& A) {
        int size = A.size();
        vector<int> B(size, 1);
        // 累积n之前的A
        for(int i = 1; i < size; ++i){
            B[i] = B[i - 1] * A[i - 1];
        }
        // 累积n之后的A
        int temp = 1;
        for(int i = size - 1; i >= 0; --i){
            B[i] *= temp;
            temp *= A[i];
        }
        return B;
    }
};