• 欢迎访问小澍的博客,编程记录,技术贴以及折腾的日常,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我的博客吧

剑指offer刷题记——构建乘积数组

Coding root 2年前 (2019-03-25) 460次浏览 已收录 0个评论

构建乘积数组

给定一个数组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]。不能使用除法。(点我直接练习

分析

思路一开始局限在了暴力法,即每个输出的数值都做一遍乘法,一个循环可以搞定,总乘法次数是n x n x n 。在参考了别人的思路以后,才豁然开朗本题的正确姿势——构建累成数组。即新构建两个数组B0,B1。使得B[i] = B0[i] x B1[i]。 这样构建后,总的乘法次数是3n,这样就少很多了。要搞清楚两个新数组如何建立也不难。依旧使用递推思路,借一张图来表示:
blob.jpg
对角线的位置及A[i]的位置,所以B0构建对角线左侧的乘积,B1则构建对角线右侧的乘积即可。构建对角线左侧即正向累成,使用正向循环;构建对角线右侧即反向累成,那么相应的,反向循环即可。

使用到的知识点

C++

数组(向量)构建

Python

暴力法,没什么知识点

题解

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
    int n = A.size();
    vector<int> B0(n,1);
    vector<int> B1(n,1);
    vector<int> B(n,1);
    for(int i = 1;i<n;++i)
        B0[i] = B0[i-1] * A[i-1];
    for(int i = n-2;i>=0;--i)
        B1[i] = B1[i+1] * A[i+1];
    for(int i = 0;i<n;++i)
        B[i] = B0[i]*B1[i];

    return B;
    }
};
class Solution:
    def multiply(self, A):
        B = A[:]
        for m in range(len(A)):
            sum = 1
            for i in range(len(A)):
                if i != m:
                    sum = sum*A[i]
            B[m] = sum
        return B

XiaoShuBlog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:剑指offer刷题记——构建乘积数组
喜欢 (0)
[gaosirgoo@foxmail.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址