剑指Offer——构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

完整代码

纯暴力思想：

#include<bits/stdc++.h>

using namespace std;

    vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        for(int i=0;i<A.size();i++){
            B.push_back(1);
            for(int j=0;j<A.size();j++){
                if(i!=j)
                    B[i]*=A[j];
            }
            
        }
        return B;
    }

int main(){
    vector<int> A,B;
    int n;
    while(cin>>n){
        A.push_back(n);
        if(cin.get()=='\n')
            break;
    }
    B=multiply(A);
    cout<<B.size()<<endl;
    for(int i=0;i<B.size();i++){
        cout<<B[i]<<endl;
    }
    return 0;
}

提交结果：

成功AC

巧妙方法：

基本思想：
如下图所示：分别计算下三角形和上三角形的值，再将上三角形和下三角形的对应元素相乘即可。

#include<bits/stdc++.h>

using namespace std;

    vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        int temp,j;//暂存上三角形的值
        if(A.size()){
            B.push_back(1);
            //计算下三角形
            for(j=1;j<A.size();j++){
                B.push_back(B[j-1]*A[j-1]);
            }
            //计算上三角形，同时计算B的最终值
            temp=1;//第n-1行
            for(j=A.size()-2;j>=0;j--){
                temp*=A[j+1];
                B[j]*=temp;
            }
        }
        return B;
    }
int main(){
    vector<int> A,B;
    int n;
    while(cin>>n){
        A.push_back(n);
        if(cin.get()=='\n')
            break;
    }
    B=multiply(A);
    cout<<B.size()<<endl;
    for(int i=0;i<B.size();i++){
        cout<<B[i]<<endl;
    }
    return 0;
}

程序分析：

相比暴力，时间复杂度O（n2）,巧妙方法时间复杂度提升了O(n).