当前位置:   article > 正文

LeetCode 238. 除自身以外数组的乘积 | Python_力扣除自身以外数组的乘积python

力扣除自身以外数组的乘积python

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


题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/product-of-array-except-self

题目

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

示例:

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

提示: 题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。

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

进阶:

你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

解题思路

思路:左右乘积列表

先看题目的提示,保证数组中任意元素的全部前缀后缀(甚至整个数组)的乘积都在 32 位整数范围内,那这里就可以不考虑数据溢出的问题。

再看说明,这个说明中表示,不能够使用除法。因为,如果要求除当前元素数组的乘积,只要先求得整个数组的乘积,除以当前元素,那么就是要求的答案。(当然,这里有个问题,如果当前元素是 0 的话,这里就要注意。不过题目不建议往这个方向考虑解决的方法,那么这里就不展开去说明了。)

现在看本篇幅使用的方法:左右乘积列表,这里需要先构造 left,right 两个数组,分别存储当前元素左侧的乘积以及右侧的乘积。

具体的构造方法:

  • 初始化两个数组 leftright。其中 left[i] 表示 i 左侧全部元素的乘积。right[i] 表示 i 右侧全部元素的乘积。
  • 开始填充数组。这里需要注意 left[0]right[lenght-1] 的值(length 表示数组长度,right 数组是从右侧往左进行填充)。
    • 对于 left 数组而言,left[0] 表示原数组索引为 0 的元素左侧的所有元素乘积,这里原数组第一位元素左侧是没有其他元素的,所以这里初始化为 1。而其他的元素则为:left[i] = left[i-1] * nums[i - 1]
    • 同样的 right 数组,right[length-1] 表示原数组最末尾的元素右侧所有元素的乘积。但因为最末尾右侧没有其他元素,所以这里 right[length-1] 也初始化为 1。其他的元素则为:right[i]=right[i+1]*nums[i+1]
  • 至于返回数组 output 数组,再次遍历原数组,索引为 i 的值则为:output[i] = left[i] * right[i]

主要在于 left 和 right 数组的构造,具体的过程如下图:

构建数组图解

具体的实现代码见【code 1】 部分。

上面的方法实现之后,时间复杂度为 O(N),空间复杂度也是 O(N) (N 表示数组的长度)。因为 构造 left 和 right 数组,两者的数组长度就是 N。

题目中的进阶部分,希望能够尝试使用常数空间复杂度完成本题。(这里不计输出数组的空间)

方法还是使用 左右乘积列表 的方法,但是这里不在单独构建 left 和 right 数组。直接在输出数组中进行构造。

具体的思路:

  • 先将输出数组当成 left 数组进行构造
  • 然后动态构造 right 数组计算结果

具体的做法:

  • 先初始化 output 数组,先当成 left 数组进行构造,那么 output[i] 就表示 i 左侧所有元素的乘积。(具体的构造方法同上)
  • 但是,这里我们不能够再单独构造 right 数组(前面说了,空间复杂度须为常数)。这里我们使用的方法是,在遍历输出答案的时候,维护一个变量 right,而变量 right 表示右侧元素的乘积。遍历更新 output[i] 的值为 output[i] * right,同时更新 right 的值为 right * nums[i] 表示遍历下一个元素右侧的元素乘积。

具体实现代码见【code 2】。

代码实现

# code 1
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        
        left = [0] * length
        right = [0] * length
        output = [0] * length

        # 先填充 left 数组
        # left 数组表示遍历时 i 左侧的乘积
        # 因为数组第一个元素左侧没有其他元素,所以 left 数组第一个元素为 1
        # left 数组接下来的元素则为原数组的第一位元素与 left 数组第一位元素的乘积,依次类推
        left[0] = 1
        for i in range(1, length):
            left[i] = nums[i-1] * left[i-1]

        # 同样的 right 数组从右往左进行填充
        # 同样数组末尾元素右侧没有其他元素,所以末尾元素值为 1
        # 右边往左的元素则为原数组与 right 数组末尾往前一位元素的乘积,依次类推
        right[length-1] = 1
        for i in range(length-2, -1, -1):
            right[i] = nums[i+1] * right[i+1]
        
        # 重新遍历,输出 output 数组
        # output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积
        # 也就是 output[i] 的值为 left[i] * right[i]
        for i in range(length):
            output[i] = left[i] * right[i]
        
        return output

# code 2
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        output = [0] * length

        # 先构建 output 为左侧乘积列表
        # 同样初始化第一个元素为 1
        output[0] = 1
        for i in range(1, length):
            output[i] = output[i-1] * nums[i-1]
        
        # 维护一个变量 right
        # 变量更新 output[i] 的值为 output[i] * right
        # 同时更新 right = right * nums[i] 表示遍历到下个元素右侧的乘积(此时遍历从右向左)
        # 初始化 right 为 1
        right = 1
        for i in range(length-1, -1, -1):
            output[i] = output[i] * right
            right = right * nums[i]
        
        return output
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
实现结果

【code 1 实现结果】

code 1 实现结果

【code 2 实现结果】

code 2 实现结果

总结

  • 先阅览题目,排除使用除法的方法。使用左右乘积列表的方法来解决问题。
  • 确定方法后,进行构建 left 和 right 数组。构造时需要注意的是 left[0]right[length-1] 两个元素。
    • left[0] 表示原数组索引为 0 左侧所有元素的乘积。而原数组索引为 0 的元素左边没有元素,所以初始化为 1。而其他元素则为:left[i] = left[i-1] * nums[i-1]
    • 同样 right[length-1] 表示原数组末尾元素右侧所有乘积。这里元素组最末尾的元素右侧没有其他元素,所以 right[length-1] 也初始化为 1。
  • 返回的输出数组 output 则为:output[i] = left[i] * right[i]
  • 前面的方法足以解决问题,题目要求进阶尝试使用常数的空间复杂度解决问题。这里还是使用左右乘积列表的思路。(题目中说明输出数组不视为额外空间)那么先用输出数组构造左乘积列表,维护一个变量 right。
  • 遍历更新 output 的数组,更新值为 output[i] * right(注意:这里遍历时从右往左遍历),更新 output 的值的同时,更新 right 的值为 right * nums[i],这里表示下一个遍历的值右侧所有元素的乘积。
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/818345
推荐阅读
相关标签
  

闽ICP备14008679号