[数据结构与算法] 【JZ66 构建乘积数组】

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【JZ66 构建乘积数组】 -> 正文阅读

[数据结构与算法]【JZ66 构建乘积数组】

描述

给定一个数组 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

输入：[1,2,3,4,5]

返回值：[120,60,40,30,24]

示例2

输入：[100,50]

返回值：[50,100]

方法：双向遍历（推荐使用）

思路：
在这里插入图片描述
如上图所示，矩阵中由对角线1将其分成了上三角和下三角。我们先看下三角，如果我们累乘的时候，B[1] 是在 B[0] 的基础上乘了新增的一个 A[0]，B[2] 是在 B[1] 的基础上乘了新增的一个 A[1]，那我们可以遍历数组的过程中不断将数组 B 的前一个数与数组A的前一个数相乘就得到了下三角中数组B的当前数。同理啊，我们在上三角中，用一个变量存储从右到左的累乘，每次只会多乘上一个数字。这样，两次遍历就可以解决。

具体做法：

step 1：初始化数组B，第一个元素为1.
step 2：从左到右遍历数组A，将数组B的前一个数与数组A的前一个数相乘就得到了下三角中数组B的当前数。
step 3：再从右到左遍历数组A，用一个数字记录从右到左上三角中的累乘，每次只会乘上一个数，同时给数组B对应部分也乘上该累乘。

图示：
在这里插入图片描述

代码：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        //初始化数组B
        vector<int> B(A.size(), 1);
        //先乘左边，从左到右
        for(int i = 1; i < A.size(); i++)
            //每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1];
        int temp = 1;
        //再乘右边，从右到左
        for(int i = A.size() - 1; i >= 0; i--){
            //temp为右边的累乘
            B[i] *= temp;
            temp *= A[i];
        }
        return B;
    }
};