leetcode-238. 除自身以外数组的乘积
除自身以外数组的乘机
给你一个整数数组 nums
,返回 数组 answer
,其中 answer[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积 。
题目数据 保证 数组 nums
之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法,且在 O(n)
时间复杂度内完成此题。
这个题最显然的解法就是把所有元素全乘起来,然后除以nums[i]
,但是除法会出现除数为0的情况,而且题目要求不能用除法。
类似前缀和,这个题用的是前缀积。
设置前缀积数组l[]
和后缀积r[]
数组,分别存放nums[i]
和nums[i]
之后所有数的乘积(不包括nums[i]
)。
注意,后缀积需要逆序求。
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 面试资料!