美文网首页
构建乘积数组

构建乘积数组

作者: Max_7 | 来源:发表于2018-10-21 23:15 被阅读0次

题目描述

给定一个数组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个元素的值为第1i-1个袁术和i+1n的乘积。那么很自然的考虑把结果分成两部分来计算。一部分是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

相关文章

  • 【数组】构建乘积数组

  • 构建乘积数组

    给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[...

  • 构建乘积数组

    给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[...

  • 构建乘积数组

    题目描述 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[...

  • 构建乘积数组

    题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i...

  • 构建乘积数组

    思路: B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1],求A数组的连乘,但不包含A[i...

  • 构建乘积数组

    题目描述 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[...

  • 构建乘积数组

    给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[...

  • 构建乘积数组

    题目描述 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[...

  • 构建乘积数组

    《剑指offer》刷题笔记。如有更好解法,欢迎留言。 关键字:数组 题目描述: 给定一个数组A[0,1,...,n...

网友评论

      本文标题:构建乘积数组

      本文链接:https://www.haomeiwen.com/subject/krgbzftx.html