Leetcode238 除自身以外数组的乘积

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

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

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

示例 1:

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

示例 2:

1
2
>输入: nums = [-1,1,0,-3,3]
>输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

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

image-20240828141028108

每个位置的结果，即为它左边的数的乘积，乘上它右边的数的乘积。
因此，我们只要申请两个数组，一个用来记录每个位置左边的乘积，和它右边的乘积，再把两个数组乘起来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        l,r = [1] * n, [1]* n
        for i in range(1,n):
            l[i] = l[i-1] * nums[i-1]
        for i in range(n-2,-1,-1):
            r[i] = r[i+1] * nums[i+1]
        res = []
        for i in range(n):
            res.append(l[i] * r[i])
        return res

优化：

image-20240828141107221

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        l = [1] * n
        for i in range(1, n):
            l[i] = l[i - 1] * nums[i - 1]
        r = 1
        for i in range(n - 1, -1, -1):
            l[i] *= r
            r *= nums[i]
        return l

转自https://leetcode.cn/problems/product-of-array-except-self/solutions/204075/gan-jue-da-bu-fen-ti-jie-du-shi-tie-dai-ma-jia-fu-/ 作为复习用