题目描述
给定一个数组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[0]*A[1]*…*A[i-1]与A[i+1]*…*A[n-1]，分别计算这两部分的值存储起来，最后再将这两部分相乘。
代码
Python(2.7.3)1
2
3
4
5
6
7
8
9
10
11
12
13# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
length = len(A)
pre_product, aft_product = [1] * length, [1] * length
for i in range(1, length):
pre_product[i] = pre_product[i - 1] * A[i - 1]
aft_product[length - i - 1] = aft_product[length - i] * A[length - i]
B = []
for i in range(length):
B.append(pre_product[i] * aft_product[i])
return B运行时间：23ms占用内存：5848k