Jianbo Dai's

mq019.除自身以外数组的乘积

 
  • Dec 05, 2020

题目链接

嗯感觉这题和一个剑指里的题目很相似，都是说不能使用除法。哦看了一眼，其实是完全一样的两个题目。这个算法的时间复杂度是O（N），空间复杂度是O（N）。啊还有一种方式是分别计算上下三角而不是一开始把一层的不同两边对齐。我们首先先算下三角below，算出来之后按逆序将nums里的数字依次相乘来算出每个位置的上三角above并且乘以对应位置下上角的数字得到结果。这样可以在维持时间复杂度的情况下将空间复杂度降到O（1）（因为数组是返回的数组所以不计入空间复杂度的计算）。

class Solution:
    def productExceptSelf1(self, nums: List[int]) -> List[int]:
        left_product, right_product = [1], [1]
        for i in range(len(nums)-1):
            left_product.append(left_product[i] * nums[i])
            right_product.append(right_product[i] * nums[len(nums)-1-i])
        return [left_product[i]*right_product[len(nums)-1-i] for i in range(len(nums))]

    def productExceptSelf2(self, nums: List[int]) -> List[int]:
        down, above = [1]*len(nums), 1
        for i in range(1, len(nums)):
            down[i] = down[i-1] * nums[i-1]
        for i in range(len(nums)-2, -1, -1):
            above *= nums[i+1]
            down[i] *= above
        return down
Search