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

蔚落 2022-05-08 11:12 172阅读 0赞

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

python3

class Solution:
        def productExceptSelf(self, nums):
            output = []
            for i in range(0, len(nums)):
                tmp = nums[0]
                nums.pop(0)
                a = 1
                for i in nums:
                    a *= i
                output.append(a)
                nums.append(tmp)
            return output

报了TLE错误，好吧很明显时间复杂度 o(n2)

python3

class Solution:
    def productExceptSelf(self, nums):
        a = [1]
        b = [1]
        for i in range(0,len(nums)-1):
            a.append(a[i]*nums[i])
            b.append(b[i]*nums[-i-1])
        output = []
        for j in range(0,len(a)):
            output.append(a[j]*b[-j-1])
        return output