java完美乘积式基础题目
题目描述
给你一个整数数组 ，返回 数组 ，其中 等于 中除 之外其余各元素的乘积 。
题目数据 保证 数组 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 时间复杂度内完成此题。
示例 1:输入: nums = 输出:
示例 2:输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
提示：
- 保证 数组 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶：你可以在 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
/blockquote>
解题思路要解决这个问题并且避免使用除法，我们可以利用前缀乘积和后缀乘积来计算每个位置的结果。我们可以按照以下步骤进行：
- 前缀乘积： 创建一个数组 ，其中 存储的是 中从 到 的元素乘积；初始化 为 ，表示没有元素前缀的乘积；遍历 数组，从左到右填充 数组。
- 后缀乘积： 创建一个变量 ，用于计算从 到数组末尾的乘积；遍历 数组，从右到左更新结果数组 对于每个 ， 是 和 的乘积。
这种方法能够在 O(n) 时间复杂度内完成计算，且空间复杂度为 O(1)，不考虑输出数组的额外空间。
复杂度分析代码实现
- 时间复杂度：O(n)，因为我们分别进行两次线性遍历，一次计算前缀乘积，一次计算后缀乘积。
- 空间复杂度：O(1)，不考虑输出数组的空间，使用了常量空间来存储中间结果。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/944.html