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

微信扫一扫,分享到朋友圈

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

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

题目来源:力扣(LeetCodehttps://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]

提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 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

实现结果

【code 1 实现结果】

【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] ,这里表示下一个遍历的值右侧所有元素的乘积。

微信扫一扫,分享到朋友圈

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

聊聊puma的DefaultDataHandler

上一篇

Python中的全局变量如何理解

下一篇

你也可能喜欢

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

长按储存图像,分享给朋友