Java基础题目完美乘积式



题目描述

给你一个整数数组 ，返回 数组  ，其中  等于  中除  之外其余各元素的乘积 。

题目数据 保证 数组 之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

Java基础题目完美乘积式

请 不要使用除法，且在  时间复杂度内完成此题。

示例 1:输入: nums = 输出:

示例 2:输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]

提示：

• 保证 数组 之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

进阶：你可以在  的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

解题思路

要解决这个问题并且避免使用除法，我们可以利用前缀乘积和后缀乘积来计算每个位置的结果。我们可以按照以下步骤进行：

1. 前缀乘积： 创建一个数组 ，其中 存储的是 中从 到 的元素乘积；初始化 为 ，表示没有元素前缀的乘积；遍历 数组，从左到右填充 数组。
2. 后缀乘积： 创建一个变量 ，用于计算从 到数组末尾的乘积；遍历 数组，从右到左更新结果数组 对于每个 ， 是 和 的乘积。

这种方法能够在 O(n) 时间复杂度内完成计算，且空间复杂度为 O(1)，不考虑输出数组的额外空间。

复杂度分析

• 时间复杂度：O(n)，因为我们分别进行两次线性遍历，一次计算前缀乘积，一次计算后缀乘积。
• 空间复杂度：O(1)，不考虑输出数组的空间，使用了常量空间来存储中间结果。

代码实现

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/24589.html