【LeetCode最详尽解答】238.除自身以外数组的乘积 Product-of-Array-Except-Self

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接:

• 238_除自身以外数组的乘积

直觉

这个问题有点棘手，我看了 Neetcode 的解释。Neetcode 非常聪明。

给定输入: nums = [1,2,3,4]

预期输出是: [24,12,8,6]

首先，我们需要构建一个结果数组来存储每个乘积值。这个数组的长度与 nums 相同。例如：

• 对于 1，乘积是 2 × 3 × 4
• 对于 2，乘积是 1 × 3 × 4
• 对于 3，乘积是 1 × 2 × 4
• 对于 4，乘积是 1 × 2 × 3

我们可以注意到，数组是根据我们要知道其乘积的值分成两部分的。所以，我们可以计算前缀乘积和后缀乘积，然后将它们相乘。

对于前缀乘积，我们可以将其初始化为 1，并在遍历整个数组时更新其值。我们将计算每个位置的前缀乘积值。怎么做呢？res[i] = prefix，然后 prefix *= nums[i]。这意味着每次我们到达 nums[i] 时，前缀已经是我们可以直接使用并更新的前缀乘积值。

对于后缀乘积，我们也可以将其初始化为 1，并应以相反的顺序计算。此时，res 已经填充了前缀乘积值。然后，对于后缀乘积，我们将更新 res[i] *= postfix，然后更新 postfix *= nums[i]。

方法

构建一个结果数组，其初始值为 [1] * len(nums)，用于存储每个数字的乘积值。乘积分为前缀和后缀。在这种情况下，前缀将初始化为 1，我们将遍历整个数组以更新结果数组和前缀值。同样，后缀将初始化为 1，我们将以相反的顺序遍历整个数组以更新结果数组和后缀值。

复杂度

• 时间复杂度:
  $$O(n)$$

  • 时间复杂度是 $O(n)$，因为我们遍历数组两次：一次计算前缀乘积，一次计算后缀乘积。每次遍历的时间复杂度都是线性的。

• 空间复杂度:
  $$O(n)$$

  • 空间复杂度是 $O(n)$，因为我们使用了一个与输入数组 nums 长度相同的额外数组 res 来存储结果。前缀和后缀变量使用的空间是常数，但额外的结果数组使空间复杂度为线性。

代码

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [1] * len(nums)
        prefix = 1
        for i in range(len(nums)):
            res[i] = prefix
            prefix *= nums[i]
        postfix = 1
        for i in range(len(nums)-1,-1,-1):
            res[i]*=postfix  
            postfix*=nums[i]
        return res