构建乘积数组

题目描述

给定一个数组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[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

难度：简单

我的回答

# -*- coding:utf-8 -*-

class Solution:

    def multiply(self, A):

        # write code here

        if len(A)<2:return

        B = [1]*len(A)

        for i in range(len(A)):

            m = A[i]

            for k in range(len(A)):

                if k!=i:

                    B[k]=B[k]*m

        return B

我的想法是，B数组中每个B[i]相当于将A数组中的A[i]镂空然后A数组中其他数字相乘。

但是这样时间复杂度太大，为O(n^2)。

牛客官方给出的题解时间复杂度低，只有O(N)。

牛客官方题解

# -*- coding:utf-8 -*-

class Solution:

    def multiply(self, A):

        # write code here

        if len(A)<2:return

        B = [1]*len(A)

        for i in range(1,len(A)):

            B[i] = B[i-1]*A[i-1]

        temp=1

        for j in range(len(A)-2,-1,-1):

            temp *= A[j+1]

            B[j] *= temp

        return B

巴特西

剑指offer二刷——数组专题——构建乘积数组

构建乘积数组

题目描述

我的回答

牛客官方题解

最新文章

热门文章