python每日一题——16除自身以外数组的乘积
题目
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
答案
这个问题可以通过使用前缀和和累积乘积来解决。我们首先计算累积乘积，然后对于每个元素，我们将累积乘积除以该元素得到结果。对于负数，我们需要注意在除以时取倒数，因为Python不直接支持负数的倒数，我们需要使用1除以该数。
以下是Python代码实现：
def product_except_self(nums):
n = len(nums)
# 初始化累积乘积数组
cumulative_product = [1] * n
# 计算累积乘积
for i in range(n):
cumulative_product[i] = cumulative_product[i-1] * nums[i] if i > 0 else nums[i]
# 计算除累积乘积
answer = [int(cumulative_product[i] / nums[i]) if nums[i] != 0 else 0 for i in range(n)]
return answer
代码解释：
- 首先，我们创建一个大小为n的累积乘积数组，初始化为1。
- 然后，我们遍历数组nums，计算累积乘积。对于每个元素，我们将前一个元素（如果有的话）的累积乘积乘以当前元素的值。
- 最后，我们创建一个新的数组answer，将累积乘积除以当前元素的值（如果元素不为0），否则设为0。这就是我们要找的答案。
这个算法的时间复杂度是O(n)，因为我们只遍历了数组一次。