LeetCode 238.除自身以外数组的乘积:前缀积x后缀积
题目
LeetCode 238. 除自身以外数组的乘积。
题目链接
思路
这道题要求不能用除法,且要在 O(n) 时间内完成。
核心公式是:结果 = 当前元素左侧所有元素的乘积 × 右侧所有元素的乘积。
我一开始想用两个数组分别存左积和右积,后来发现可以用一个动态变量来节省空间。
关键点
- 端点处理:第一个元素左侧乘积为 1,最后一个元素右侧乘积为 1。
- 用动态变量
leftProduct/rightProduct累积。 - 进阶:用输出数组本身当左积数组,省一个 O(n) 空间。
代码
这里贴我的 Java 代码:
1 | class Solution { |
复杂度
- 时间复杂度:O(n),其中 n 是数组长度。两次遍历数组。
- 空间复杂度:O(1),如果不算输出数组的话,只用了常数个变量。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Skiow的博客!