当前位置：首页 > news >正文

leetcode_238:除自身以外数组的乘积

news 文章来源：https://blog.csdn.net/D2510466299/article/details/142685582 2025/1/10 21:43:37

给你一个整数数组 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]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

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

步骤1：定义计算问题性质

问题描述：

给定一个整数数组 nums，要求返回一个新的数组 answer，其中 answer[i] 等于数组 nums 中除 nums[i] 以外的所有元素的乘积。重要的限制条件包括：

不允许使用除法。
时间复杂度必须为 O(n)。
保证所有前缀和后缀乘积均在32位整数范围内。

输入输出条件：

输入: 整数数组 nums，长度范围为 2 <= nums.length <= 10^5，元素范围为 -30 <= nums[i] <= 30。
输出: 新的整数数组 answer，其每个元素等于 nums 数组中除当前索引元素外其他所有元素的乘积。

边界条件：

数组中的元素为零：当有多个元素为零时，除了包含零的元素，其他元素的乘积都为零。
长度为2的数组：需要特别考虑只有两个元素的情况。

步骤2：分解问题

解决思路：

为了在 O(n) 时间复杂度内完成该任务，并且不使用除法，我们可以通过两次遍历数组分别计算每个元素的前缀乘积和后缀乘积，从而构造出最终的答案。

具体思路如下：

前缀积：我们可以先从左往右遍历数组 nums，并逐步计算当前元素的前缀积，存储在数组 answer 中。前缀积表示从数组开头到 i-1 位置的所有元素的乘积。
后缀积：在计算完前缀积后，再从右往左遍历数组 nums，并逐步计算当前元素的后缀积，并与已经存储的前缀积相乘得到最终结果。后缀积表示从 i+1 到数组末尾的所有元素的乘积。

代码实现过程中的两个关键点：

时间复杂度：遍历两次数组，前缀积和后缀积的计算均为 O(n)，符合题目要求。
空间复杂度：除了结果数组 answer 外，我们只需要常数空间来保存后缀积，因此额外空间复杂度为 O(1)。

步骤3：C++代码实现

注释解释：

初始化结果数组 answer，长度为 n，初始值为1。
第一遍从左到右遍历 nums，计算每个位置的前缀积，并将其保存在 answer 数组中。
第二遍从右到左遍历 nums，在计算每个位置的后缀积的同时，将其乘以已经计算好的前缀积，从而得到最终的结果。

步骤4：算法的启发

1. 优化思路：

这道题的优化思路体现在如何有效利用空间和避免重复计算。通过利用前缀积和后缀积的思想，可以在一次遍历中逐步构建结果，而不需要像暴力解法那样嵌套循环。

2. 效率提升：

该算法非常适合处理大规模数据集，因为它的时间复杂度为 O(n)，且额外的空间复杂度为 O(1)。这意味着它可以在现代计算环境中高效地处理包含10万或更多元素的大数据集。

3. 边界条件处理：

特别需要考虑数组中可能存在的零的情况。该解法天然能够处理零的存在，因为前缀和后缀乘积的分离，使得零所在的位置不会影响其他位置的乘积计算。

步骤5：实际应用场景

1. 场景：大规模数据处理中的除法优化

在某些金融场景中，我们可能需要计算投资组合中每个资产的权重，权重是基于其他资产的价格总和与当前资产的价格进行比较。直接使用除法可能导致精度损失，特别是在涉及小数或大量资产时。而通过类似前缀后缀乘积的方式，我们可以避免直接除法，减少精度误差。

2. 场景：电商推荐系统中的权重分配

在电商推荐系统中，当我们为一个产品分配推荐权重时，往往需要考虑其他产品的相关性及影响因素。这时，可以借鉴该算法的前后缀思路，快速计算出某个产品相对于其他产品的影响力。

3. 具体实现方法：

步骤1：获取所有产品的基础权重或评分。
步骤2：从评分数组中去除某个产品，然后计算其相对于其他产品的权重乘积。
步骤3：通过前缀和后缀积的算法高效完成权重分配，避免重复计算，提升系统效率。

总结

该题目通过计算前缀积和后缀积，有效解决了“除自己外的乘积”的问题，且在时间和空间复杂度上都达到了最优。算法思想可用于多种实际场景，特别是在需要优化大规模数据计算或避免除法操作的场景中，具有很好的应用价值。