[1,2,3,4,5]
[120,60,40,30,24]
[100,50]
[50,100]
# -*- 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
# -*- 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
# -*- 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
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
# -*- 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
# -*- 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
# -*- 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
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的各元素几个
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
<分析>： 解释下代码，设有数组大小为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; } };