Python练习题：实现除自身以外元素的乘积

Python练习题：实现除自身以外元素的乘积

题目

给定一个长度为 n 的整数列表 nums，其中 n > 1，返回输出列表 res ，其中 res[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

例如：

给定一个列表：[1, 2, 3, 4]，返回结果：[24, 12, 8, 6]

注意：实现过程中，不允许使用 除法 ，且要求时间复杂度为O(n)

实现思路

遍历列表，对于遍历到的当前元素，如果要计算出除其自身以外整数的乘积，我们只需要分别求出 左侧所有元素的乘积 和 右侧所有元素的乘积 即可。

假设给定列表为：[1, 2, 3, 4]，其具体计算过程如下：

首先，正序遍历，分别求出每个元素左侧的所有元素的乘积，结果保存到 left_product_list 接着，倒序遍历，分别求出每个元素右侧的所有元素的乘积，结果保存到 right_product_list 最后，对每个遍历到的元素，最终乘积结果 = 左乘积 * 右乘积，把结果保存到一个列表，最终返回即可

代码实现

def productExceptSelf(nums): res = [] left_product_list, right_product_list = [1], [1] left_product, right_product = 1, 1 for i in range(1, len(nums)): # 从第一个元素开始，计算每个元素左侧的所有元素的乘积 left_product *= nums[i - 1] left_product_list.append(left_product) for i in range(len(nums) - 2, -1, -1): # 从倒数第二个元素开始，计算每个元素右侧的所有元素的乘积 right_product *= nums[i + 1] right_product_list.append(right_product) for i in range(len(nums)): # 注意 left_product_list 是正序计算，right_product_list 是倒序计算 left, right = left_product_list[i], right_product_list[len(nums) - 1 - i] res.append(left * right) return

上面的实现方式中，我们专门定义了两个列表：​​left_product_list​​​、​​right_product_list​​，分别记录左侧元素乘积、右侧元素乘积，这里的空间复杂度是 O(n)，如果我们不考虑返回列表空间的话，那么其实可以针对上方代码进行优化，让其空间复杂度降到 常数级别 O(1)：

def productExceptSelf(nums): res = [1] * len(nums) left_product, right_product = 1, 1 for i in range(1, len(nums)): # 从第一个元素开始，计算每个元素左侧的所有元素的乘积 left_product *= nums[i - 1] res[i] *= left_product for i in range(len(nums) - 2, -1, -1): # 从倒数第二个元素开始，计算每个元素右侧的所有元素的乘积 right_product *= nums[i + 1] res[i] *= right_product return

上面的实现方式中，我们不再专门使用额外的列表来保存左右侧元素乘积，而是将最终返回列表设置为一个固定长度的列表，接着直接修改列表中的元素值，如此一来，如果不考虑返回列表空间的前提下，其空间复杂度就降到 O(1)。

从上面的代码中，可以发现我们对列表进行了2次遍历，第一次正序遍历是为了计算左乘积，第二次倒序遍历是为了计算右乘积，在这里其实我们也可以继续优化，仅通过一次遍历来完成，最终优化后代码如下：

'''学习中遇到问题没人解答？小编创建了一个Python学习交流群：711312441寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！'''def productExceptSelf(nums): """ 针对 [1, 2, 3, 4] ，遍历过程中，每个元素的左右累积均相乘 i=0, res[0]乘左累积，res[3]乘右累积； i=1, res[1]乘左累积，res[2]乘右累积； i=2, res[2]乘左累积，res[1]乘右累积； i=3, res[3]乘左累积，res[0]乘右累积 """ res = [1] * len(nums) left_product, right_product = 1, 1 for i in range(len(nums)): res[i] *= left_product left_product *= nums[i] # 下标 i 位置元素的左侧所有元素的累积 res[len(nums) - 1 - i] *= right_product right_product *= nums[len(nums) - 1 - i] # 下标 len - 1 - i 位置元素的右侧所有元素的累积 return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。