构建乘积数组

题目描述

给定一个数组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个元素的值为第1_{i-1个袁术和i+1}n的乘积。那么很自然的考虑把结果分成两部分来计算。一部分是i前面的部分，一部分是i后面的部分。
然后注意一下开头和结尾的处理就可以。

代码

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B = self.helper(A)
        return B
    def helper(self,nums):
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return nums[0]
        forward = []
        backward = [1] * (len(nums) + 1)
        forward.append(nums[0])
        backward[len(nums) - 1] = nums[len(nums) - 1]
        B = []
        val_0 = 1
        for i in range(len(nums)):
            val_0 = val_0 * nums[i]
        B.append(val_0)
        for i in range(1, len(nums)):
            val_1 = forward[i - 1] * nums[i]
            forward.append(val_1)
        for i in range(len(nums) - 2, -1, -1):
            val_2 = backward[i + 1] * nums[i]
            backward[i] = val_2
        for i in range(1, len(nums)):
            val_3 = forward[i - 1] * backward[i + 1]
            B.append(val_3)
        return B