算法练习14——除自身以外数组的乘积

LeetCode 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

蛮力法：前后缀列表

不能使用除法，先来最暴力的

纯循环：双重循环，每次计算answer[i]时需要整个遍历一次nums，需要一个长度为n的数组存储结果，题意认为不被视为额外空间，但时间复杂度要求不满足

优化一下时间复杂度，上策是保证空间复杂度不变的情况下降低时间复杂度，下策是提高空间复杂度而降低时间复杂度，通常先出下策，再优化为上策

前缀+后缀列表，额外使用两个长度为n的数组，分别计算answer[i]的前缀和后缀，前缀和后缀的计算只需要分别遍历一次nums，最后遍历一次前缀和后缀列表即可求得乘积，此时时间复杂度就达到了要求

再优化一下，需要额外两个长度为n的空间复杂度，此时在复用程度低的answer数组上做文章，依然是前缀后缀列表，计算前缀列表直接存到answer数组中，然后动态计算后缀数组的同时，将当前计算出来的nums[i]的后缀tmp与前缀answer[i]相乘即可

Python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n

        tmp = 1
        for i in range(1, n):
            res[i] = tmp * nums[i-1]
            tmp = res[i]
        
        tmp = 1
        for i in range(n - 2, -1, -1):
            res[i] *= nums[i + 1] * tmp
            tmp = nums[i + 1] * tmp
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Go

func productExceptSelf(nums []int) []int {
	var n = len(nums)
	var res = make([]int, n)
	res[0] = 1

	for i := 1; i < n; i++ {
		res[i] = res[i-1] * nums[i - 1]
	}

	tmp := 1
	for i := n - 1; i > -1; i-- {
		res[i] *= tmp
		tmp *= nums[i]
	}
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16