剑指 构建乘积数组

构建乘积数组

http://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46

对于每一个B[i]值都分为左右两段的乘积,分别循环得到他们的结果。 O(n^2)

class Solution:
    def multiply(self, A):
        # write code here
        if len(A)==1:
            return -1
        length=len(A)


        B=[0 for _ in range(length) ]
        def multi_result(start,end):
            result=1
            if start>=length:
                return 1
            for i in range(start,end):
                result*=A[i]
            return result
        for i in range(length):
            front=multi_result(0, i)
            later=multi_result(i+1,length)
            B[i]=front*later

        return B

分析,将B[i]的结果分为左右,发现左右分别与其上一个结果有关,所以每次不用重复遍历,只需乘上当前的数值就行,所以从下三角到上三角遍历两次,最终得到结果。

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if len(A)==0:
            return -1
        B=[1 for _ in range(len(A))]
        temp=[1 for _ in range(len(A))]
        temp_=[1 for _ in range(len(A))]
        for i in range(1,len(A)):
           temp[i]=temp[i-1]*A[i-1]
           B[i]*=temp[i]


        for i in range(len(A)-2,-1,-1):
            temp_[i]=temp_[i+1]*A[i+1]
            B[i]*=temp_[i]

        return B

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 00:05
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 14:39
门头沟学院_2024
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议