数据结构学习 jz66 构建乘积数组

关键词：数学 双指针

方法一：这个题目我一开始做不知道不能用除法。我做的：[ 用时: 12 m 12 s ] 用了除法 分类讨论

方法二：后来看了提示，双指针，两边各开始乘。

方法三：然后又看了答案可以节省空间。

题目：按规则计算统计结果

方法一：

用了除法 分类讨论

思路：

统计是否有零，不然没法除。

count_0//如果有0，那么true

求所有数的乘积：

res记录所有数（除了第一个遇到的0）的乘积结果。

如果只有一个0，那么除了它以外的数的乘积就是res。

如果有超过一个0，那么全部结果都是0。

        for(const auto&x:arrayA)
        {
            if(x==0&&count_0==0)
            {
                 count_0++;
                 continue;
            }
            res*=x;
        }

求结果：

如果没有0，那么正常除。

如果有0，则0那个位置的结果就是res，除了0以外的数的结果都是0。

        for(const auto&x:arrayA)
        {
            if(count_0==0)
                arrayB.push_back(res/x);
            else
            {
                if(x==0)
                    arrayB.push_back(res);
                else
                    arrayB.push_back(0);  
            }
        }

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        int res=1;
        int count_0=0;
        for(const auto&x:arrayA)
        {
            if(x==0&&count_0==0)
            {
                 count_0++;
                 continue;
            }
            res*=x;
        }
        vector<int> arrayB;
        for(const auto&x:arrayA)
        {
            if(count_0==0)
                arrayB.push_back(res/x);
            else
            {
                if(x==0)
                    arrayB.push_back(res);
                else
                    arrayB.push_back(0);  
            }
        }
        return arrayB;
    }
};

方法二：

看了答案的提示：左右两边各开始乘，得到从左到右和从右到左的两个向量

思路：

用两个向量记录从左到右累积和从右到左累积的结果。

然后求res的时候，左右各乘结果。

arrayA	2	3	4	5	6
l2r	2	2*3	2*3*4	2*3*4*5	2*3*4*5*6
r2l	6	6*5	6*5*4	6*5*4*3	6*5*4*3*2
res	R2l[3]	l2r[0]*r2l[2]	l2r[1]*r2l[1]	l2r[2]*r2l[0]	l2r[3]

复杂度计算：

时间复杂度O(n)

空间复杂度O(n) 2n，两个向量存累积结果

?代码：

class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        vector<int> res;
        if(arrayA.empty()) return res;
        if(arrayA.size()==1) return arrayA;
        vector<int> l2r,r2l;
        l2r.push_back(arrayA[0]);//初始化
        r2l.push_back(arrayA[arrayA.size()-1]);//初始化
        for(int i=1;i<arrayA.size();++i)//左到右累积
        {
            l2r.push_back(l2r[i-1]*arrayA[i]);
        }
        for(int i=1;i<arrayA.size();++i)//右到左累积
        {
            r2l.push_back(r2l[i-1]*arrayA[arrayA.size()-i-1]);
        }
        for(int i=0;i<arrayA.size();++i)//求res
        {
            int temp=1;
            if(i>0) temp*=l2r[i-1];//如果i=0，就不用左边
            if(i<arrayA.size()-1) temp*=r2l[arrayA.size()-i-2];//如果i在最右边，就不用右边
            res.push_back(temp);
        }
        return res;
    }
};

方法三：

看了k神的答案写的 和方法二一样但节省了空间

思路：

具体看k神的图解。

主要是先乘下三角，再乘上三角，即可。

下三角：

上三角：

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)?

代码：

class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        vector<int> res;
        if(arrayA.empty()) return res;
        if(arrayA.size()==1) return arrayA;
        res.push_back(1);
        for(int i=1;i<arrayA.size();++i)//下三角
        {
            res.push_back(res[i-1]*arrayA[i-1]);
        }
        int temp=1;
        for(int i=arrayA.size()-2;i>=0;--i)//上三角
        {
            temp*=arrayA[i+1];
            res[i]*=temp;
        }

        return res;
    }
};