本文主要是介绍【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 ) O(n) O(n),因为我们遍历数组两次:一次计算前缀乘积,一次计算后缀乘积。每次遍历的时间复杂度都是线性的。
-
空间复杂度:
O ( n ) O(n) O(n)- 空间复杂度是 O ( n ) O(n) O(n),因为我们使用了一个与输入数组
nums
长度相同的额外数组res
来存储结果。前缀和后缀变量使用的空间是常数,但额外的结果数组使空间复杂度为线性。
- 空间复杂度是 O ( n ) O(n) O(n),因为我们使用了一个与输入数组
代码
class Solution(object):def productExceptSelf(self, nums):""":type nums: List[int]:rtype: List[int]"""res = [1] * len(nums)prefix = 1for i in range(len(nums)):res[i] = prefixprefix *= nums[i]postfix = 1for i in range(len(nums)-1,-1,-1):res[i]*=postfix postfix*=nums[i]return res
这篇关于【LeetCode最详尽解答】238.除自身以外数组的乘积 Product-of-Array-Except-Self的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!