首页 > 试题广场 >

构建乘积数组

[编程题]构建乘积数组

热度指数：311705 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个数组 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 \le n \le 10 \$ ，数组中元素满足 $|val| \le 10 \$

示例1

输入

[1,2,3,4,5]

输出

[120,60,40,30,24]

示例2

输入

[100,50]

输出

[50,100]

算法知识视频讲解

牛客题解官

发表于 2020-06-01 16:53:33

精华题解题目的主要信息：给定一个数组A，要求返回数组B，数组B每个元素等于数组A所有元素除了对应下标以外的全部元素的乘积即B[i]=A[0]∗A[1]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1]B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]B[i] 展开全文

不是江小白

发表于 2021-06-23 14:19:11

精华题解 1.思路前提一开始掌柜拿到这题的时候还是有点懵逼的，后来一看示例就开始懂了。题目的三句话需要注意后面这两句话： “不能使用除法。”有朋友肯定会疑问？为何不可用除法？因为你去看示例后就知道，如果是除法，直接这题就变成B[i] = (A[0] * A[1] * ... *A[n-1]) / A[i 展开全文

江南好___

发表于 2021-06-24 22:28:42

精华题解描述题目描述给定一个数组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- 展开全文

Maokt

发表于 2021-06-28 14:05:39

精华题解算法思想一：表格分区，两次遍历解题思路： B[0]= 1 A[1] A[2] ... A[n-2] 展开全文

青梅煮酒不说话

发表于 2019-11-26 21:52:57

题目给定一个数组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[i] = A[0]A[1]...A[i-1]A[i+1]...A[n-1]，即除去 A 展开全文

法拉利201903231900848

发表于 2019-08-05 23:45:57

//给定一个数组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]。不能使用除法。 class Solution { public: 展开全文

学无止境呀～

发表于 2019-09-11 20:42:17

51. 构建乘积数组题目描述给定一个数组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的时候，A[i]赋值为1，计算B[i]。时展开全文

冰梦IceDream

发表于 2019-09-14 09:08:33

题目描述给定一个数组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]。不能使用除法。实现思路既然不能用乘法，分析题目，我们可以将乘积拆为两项。即: C[i] = A[0] * 展开全文

扣得皮

发表于 2020-02-04 15:49:44

如上图所示先根据offer上的算法，先计算下三角的乘积，再计算上三角的乘积并且拼接 import java.util.ArrayList; public class Solution { public int[] multiply(int[] A) { int length= 展开全文

Ironxin

发表于 2020-03-04 22:28:51

题目描述给定一个数组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 展开全文

中工升达预备毕业生

发表于 2019-12-15 17:33:59

【书上的题解真妙】 public class Solution { public int[] multiply(int[] A) { if (A == null || A.length <= 0) { return null; } 展开全文

SandMonth

发表于 2021-10-13 00:43:25

构建乘积数组给定一个数组A[0,1,...,n−1]A[0,1,...,n-1]A[0,1,...,n−1],请构建一个数组B[0,1,...,n−1]B[0,1,...,n-1]B[0,1,...,n−1],其中B中的元素B[i]=A[0]∗A[1]∗...∗A[i−1]∗A[i+1]∗... 展开全文

practice666

发表于 2020-03-24 23:40:21

思路：i不为0的情况下，B[i]的值等于A[0]A[1]...A[i-1]A[i+1]...A[n-1]，也就是说，除了A[i]之外，剩下的A数组中的数都连续相乘。因此考虑将整个相乘阶段分为i以前和i以后，使用两个for循环做连续相乘，最后得到结果。 public class Solution { 展开全文