首页 > 试题广场 >

构建乘积数组

[编程题]构建乘积数组
  • 热度指数：313421 时间限制：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

输入

[1,2,3,4,5]

输出

[120,60,40,30,24]
示例2

输入

[100,50]

输出

[50,100]
算法知识视频讲解
添加回答
推荐
张佃鹏头像 张佃鹏 
<分析>：
解释下代码，设有数组大小为5。
对于第一个for循环
第一步：b[0] = 1;
第二步：b[1] = b[0] * a[0] = a[0]
第三步：b[2] = b[1] * a[1] = a[0] * a[1];
第四步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2];
第五步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];
然后对于第二个for循环
第一步
temp *= a[4] = a[4];  
b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];
第二步
temp *= a[3] = a[4] * a[3];
b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];
第三步
temp *= a[2] = a[4] * a[3] * a[2];  
b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];
第四步
temp *= a[1] = a[4] * a[3] * a[2] * a[1];  
b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];
由此可以看出从b[4]到b[0]均已经得到正确计算。
class Solution {
public:
  vector<int> multiply(const vector<int>& A) {
  vector<int> vec;
  int sz=A.size();
  if(sz==0)
   return vec;
  vec.push_back(1);
  for(int i=0;i<sz-1;i++)
   vec.push_back(vec.back()*A[i]);
  int tmp=1;
  for(int i=sz-1;i>=0;i--)
  {
   vec[i]=vec[i]*tmp;
   tmp=tmp*A[i];
  }
  return vec;
    }
};

编辑于 2015-08-25 11:17:49 回复(54)
Python
王大涛头像 王大涛
暴力求解！
class Solution:
    def multiply(self, A):
        # write code here
        B = []
        Ji1 = 1
        Ji2 = 1
        for i in range(1 ,len(A)):
            Ji1 *= A[i]
        B.append(Ji1)
        for j in range(1 , len(A)-1):
            Ji = 1
            for m in range(0 , j):
                Ji *= A[m]
            for M in range(j+1 , len(A)):
                Ji *= A[M]
            B.append(Ji)
        for J in range(0 , len(A)-1):
            Ji2 *= A[J]
        B.append(Ji2)
        return B
发表于 2021-05-13 20:59:01 回复(0)
Python
kk-li头像 kk-li
class Solution:
    def multiply(self, A):
        # write code here
        B = []
        for i in range(len(A)):
            out = 1
            for j, value in enumerate(A):
                if j == i:
                    continue
                out *= value
            B.append(out)
        return B
发表于 2021-05-08 16:23:55 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B=[]
        n=len(A)
        b=1
        if not A&nbs***bsp;n==1:
            return B
        for i in range(n):
            for j in range(n):
                if j!=i:
                    b*=A[j]
            B.append(b)
            b=1
        return B

发表于 2021-05-05 23:52:13 回复(0)
Python
Hiroi头像 Hiroi
Python 建立一个函数，计算除了A[i]之外的其他数的乘积，循环i从0到n-1，结果放到B中。特殊情况是len(A)==0或1，B=[]。 
# -*- coding:utf-8 -*-
class Solution:
    def multi_i(self, i, A):
        res = 1
        for j in range(len(A)):
            if j==i:
                continue
            else:
                res = res*A[j]
        return res
    def multiply(self, A):
        # write code here
        B = []
        if len(A)<2:
            return B
        for i in range(len(A)):
            B.append(self.multi_i(i,A))
        return B


发表于 2021-04-17 22:37:49 回复(0)
Python
学习不能停下呀头像 学习不能停下呀 
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        #原来的思路是实现一个不用除法运算符的除法来计算
        #后来参考了一些实现发现用分治法的方法比较好，时间复杂度可以降低到2o(N),和除法比较差不多
        #其实也不全是分治法，也有动态规划的思想，利用之前乘积对于后续运算有用，然后将一个B[I]的乘法运算划分为两部分实现
        if len(A)<2:
            return None
        B=[1]
        for i in range(1,len(A)):#left[i]
            B.append(B[i-1]*A[i-1])
        temp=1#right[i],right[n-1]=1
        for i in range(len(A)-2,-1,-1):
            temp*=A[i+1]
            B[i]*=temp
        return B
            
            

发表于 2021-03-15 17:19:18 回复(0)
Python
西南交大巨可爱头像 西南交大巨可爱
# python 使用循环解决
class Solution:
    def multiply(self, A):
        # write code here
        B = []
        for i in range(len(A)):
            B.append(1) 
        for i in range(len(A)):
            for j in range(len(A)):
                if i == j:
                    pass
                if i != j:
                    B[i] *= A[j] 
        return B
发表于 2021-03-11 19:08:11 回复(0)
Python
在下小6头像 在下小6

python两种解法：

# -*- coding:utf-8 -*-
"""
B[i] = A[0]*...A[n-1]/A[i] 本题不能用除法
思路1:直接做呗，但是这样时间复杂度为O(n*n)
"""
class Solution:
    def multiply(self, A):
        B = {}
        for i in range(len(A)):
            B[i] = 1
            for j in range(len(A)):
                if j != i:
                    B[i] *= A[j]
        return B

"""
思路2:B[i]的计算可以写成：
left[i] = A[0]*A[1]*...*A[i-1]
right[i] = A[i+1]*...*A[n-1]=A[i+1]*A[i+2]...*A[n-1] = right[i+1]*A[i+1]

left[i+1] = A[0]*A[1]*...*A[i-1]*A[i]=left[i]*A[i]
right[i+1] = A[i+2]*...*A[n-1]

left[0] = 1
right[0] = A[1]*A[2]*...*A[n-1]

left[n-1]= A[0]*A[1]*...*A[n-2]
right[n-1] = 1

B[i]=A[0]*A[1]*...*A[i-1] * A[i+1]*...*A[n-1]
    =left[i]*right[i]
    =left[i]*right[i+1]*A[i+1]

由此发现，计算B的时候是有重复部分的，所以可以先计算left和right,时间复杂度为O(n)；
"""
class Solution:
    def multiply(self, A):
        n = len(A)
        B = {}
        left = [1 for i in range(n)]
        right = [1 for i in range(n)]
        for i in range(1,n):
            # 构建left数组：left[i] = left[i-1]*A[i-1]
            left[i] = left[i-1]*A[i-1]
            # 构建right数组：right[i] = right[i+1]*A[i+1]
            right[n-1-i] = right[n-i]*A[n-i]
        for i in range(n):
            B[i] = left[i] * right[i]
        return B
发表于 2021-02-18 14:21:24 回复(0)
Python
求offer砸过来头像 求offer砸过来
求助：python 环境下报错，请问错在哪里？ 
class Solution:
    def multiply(self, A):
        # wa=[1,2,3,4,5]
        b=[]
        for i in range(len(A)):
            b.append(1)
        for i in range(len(A)):
            for j in range(len(A)):
                    b[i]=A[j]*b[i]
            b[i]=int(b[i]/A[i])
        print(b)


发表于 2021-02-03 10:10:15 回复(0)
Python
事事顺利天天开心头像 事事顺利天天开心 
class Solution:
    def multiply(self,A):
        B=[]

        for n in range(len(A)):
            MUL = 1
            for i in range(len(A)):
                if i ==n:
                    continue
                else:
                    MUL=MUL*A[i]

            B.append(MUL)
        print(B)
        return B

A=Solution()
A.multiply(A=[1,2,3,4,5])

发表于 2021-01-31 11:15:49 回复(0)
Python
12313242头像 12313242 
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        head = []
        tail = []
        front = 1
        after = 1
        for i in range(len(A)):
            if i == 0:
                head.append(front)
                tail.append(after)
            else:
                front *= A[i-1]
                after *= A[-i]
                head.append(front)
                tail.append(after)
        B = []
        for j in range(len(head)):
            multi = head[j] * tail[-(j+1)]
            B.append(multi)
        return B

编辑于 2020-10-30 00:05:28 回复(0)
Python
小牛向前冲，！头像 小牛向前冲，！
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B = []
        for j in range(len(A)):
            c=A.pop(j)
            a=1
            for i in range(len(A)):
                a=A[i]*a
            B.append(a)
            A.insert(j,c)
        return B
发表于 2020-10-08 20:22:51 回复(0)
Python
Weirdom头像 Weirdom
欢迎采纳，哈哈哈
class Solution:
    def multiply(self, A):
        B = []
        for i in range(0, len(A)):
            sum = 1
            for j in range(0, len(A)):
                if i != j:
                    sum *= A[j]
                B.append(sum)
        return B

发表于 2020-08-13 15:09:49 回复(0)
Python
小白HZC头像 小白HZC
解题思路如上： 
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        length = len(A)
        B = []
        for i in range(length):
            newA = A+[]
            newA[i]=1
            result = 1
            for j in newA:
                result *= j
            B.append(result)
        return B



编辑于 2020-07-25 16:09:17 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B = [1] * len(A)
        for i in range(0,len(A)):
            for j in range(0,len(A)):
                if i != j:
                    B[i] = B[i] * A[j]
        return B
注意：
1，题目的要求，即B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]即维度不乘以A中自己对应的那个下标的位置的数。
2，range(0,n)表示0、1、2.....n-1

编辑于 2020-07-22 17:12:45 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa
# -*- coding:utf-8 -*-
class Solution:
    def cheng(self,A,i):
        AA=[0]*len(A)
        for ii in range(len(A)):
            AA[ii]=A[ii]
        AA.pop(i)
       
        if 0 in AA:
            return 0
        re=1
        for iii in range(len(AA)):
            if AA[iii]!=1:
                re=re*AA[iii]
            else:
                pass
        return re
           
    def multiply(self, A):
        if len(A)==0:
            return []
        if len(A)==1:
            return A
        B=[0]*len(A)
       
        for i in range(len(B)):
            B[i]=self.cheng(A,i)
        return B
           
        # write code here
发表于 2020-05-27 21:20:26 回复(0)
Python
ssssxt头像 ssssxt 
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code 
        n = len(A)
        if n <2:
            return A
            
        b1 = [1] * n
        for i in range(n-2, -1, -1):
            b1[i] = b1[i+1] * A[i+1]
        b2 = [1] * n
        b = [1] * n
        b[0] = b1[0]
        for i in range(1, n):
            b2[i] = b2[i-1] * A[i-1]
            b[i] = b1[i] * b2[i]
        return b
编辑于 2020-05-22 22:00:46 回复(1)
Python
袁长安头像 袁长安
相当于一个新的数组和原数组长度一致。
在A数组中，乘以除了i位置上的数字得到的积，添加进B数组相同的位置上， 代码如下：
新建了一个新的列表，里面储存了除了当前位置之外的所有元素。遍历相乘，添加进新列表即可。
class Solution:
    def multiply(self, A):
        B = []
        for i in range(len(A)):
            tem = A[:i] + A[i+1:]
            res = 1
            for j in tem:
                res *=j
            B.append(res)
        return B
        

发表于 2020-05-19 12:35:21 回复(0)
Python
啊啊啊啊啊哈头像 啊啊啊啊啊哈
class Solution:
    def multiply(self, A):
        # write code here
        b=[]
        for i in range(len(A)):
            temp=1
            for j in range(len(A)):
                if j!=i:
                    temp*=A[j]
            b.append(temp)
        return b
发表于 2020-04-15 11:54:47 回复(0)
Python
夜深忽梦少年事丶头像 夜深忽梦少年事丶 
class Solution:
    def multiply(self,A):
    # write code here
        B = []
        for i in range(len(A)):
            b = 1
            for j in range(len(A)):
                if j == i:
                    continue
                else:
                    b = b * A[j]
            B.append(b)
        return B

个人感觉这个方法比较简单点

发表于 2020-03-24 18:58:50 回复(0)
Python
Evonne_hu头像 Evonne_hu 
class Solution:
    def multiply(self, A):
        # write code here
        left = [1]
        right = [1]
        B = []
        for i,v in enumerate(A):
            left.append(left[-1] * v)
            right.append(right[-1] * A[-(i+1)])
        for i in range(len(A)):
            B.append(left[i] * right[-(i+2)])
        return B
借鉴剑指offer思路，遍历一遍A，生成自左向右、自右向左的连乘序列。最后循环生成B的各元素几个
发表于 2020-03-22 00:34:19 回复(0)
提交观点

问题信息

数组
难度：
70条回答 105944浏览

热门推荐

通过挑战的用户

查看代码

相关试题

构建乘积数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号