剑指OFFER_构建乘积数组

2021-04-19 00:28

阅读：332

标签：load i+1 元素 ++ off multi typedef 描述说明

剑指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]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

思路

由于不让使用除法，我只能想到挨个相乘的笨办法，但是这种办法肯定会超时。我没找到更好的办法的情况下去看了题解：

技术图片

题目把A[i]分为了左右两个部分，left=A[0] * ……A[i-1]；right=A[i+1] * …… A[n-1]，如同图中所示。

那么就可以把蓝色区域和红色区域作为数组计算出来，然后构建B[i]的时候将左右两个部分相乘即可，代码如下：

代码

typedef vector vec;
class Solution {
public:
    vector multiply(const vector& A) {
        int len = A.size();
        vec ans = vec(len);
        vec front_order = vec(len);
        vec back_order = vec(len);
        
        front_order[0] = back_order[len-1] = 1;
        for (int i=1; i=0; i--) {
            back_order[i] = back_order[i+1]*A[i+1];
        }
        for (int i=0; i

剑指OFFER_构建乘积数组

标签：load i+1 元素 ++ off multi typedef 描述说明

原文地址：https://www.cnblogs.com/sakurapiggy/p/13291904.html

上一篇：【spring使用@Async注解异步处理】

下一篇：springboot使用hibernate validator校验

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：剑指OFFER_构建乘积数组
文章链接：http://soscw.com/index.php/essay/76428.html

亲，登录后才可以留言！

剑指OFFER_构建乘积数组

剑指OFFER_构建乘积数组

题目描述

思路

代码

评论

热门文章

推荐文章

最新文章

置顶文章