leetcode
leetcode 201 ~ 250
除自身以外数组的乘积

除自身以外数组的乘积

难度:

标签:

题目描述

给你一个整数数组 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) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)

代码结果

运行时间: 26 ms, 内存: 21.6 MB


/*
 * Problem: Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
 * Using Java Streams, we can utilize the map function to generate the product of elements except for the current one.
 */
 
import java.util.Arrays;
 
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftProducts = new int[n];
        int[] rightProducts = new int[n];
        
        leftProducts[0] = 1;
        for (int i = 1; i < n; i++) {
            leftProducts[i] = leftProducts[i - 1] * nums[i - 1];
        }
        
        rightProducts[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProducts[i] = rightProducts[i + 1] * nums[i + 1];
        }
        
        return Arrays.stream(nums)
                     .map(i -> leftProducts[i] * rightProducts[i])
                     .toArray();
    }
}
 

解释

方法:

这个题解的思路是用前缀积和后缀积的方式来计算除自身以外数组的乘积。首先用一个数组 answer 存储结果,初始化 answer[0] 为 1,表示索引 0 左侧的乘积为 1。然后从左到右遍历数组,对于索引 i,answer[i] 等于 answer[i-1] 乘以 nums[i-1],即索引 i 左侧数字的乘积。接着从右到左遍历数组,用变量 R 记录索引 i 右侧数字的乘积,answer[i] 等于其本身乘以 R,然后 R 乘以 nums[i],继续更新到下一个位置。最终 answer 数组就是所求的结果。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在题解中提到的算法,初始化`answer[0]`为1是基于什么考虑?
初始化`answer[0]`为1是因为需要代表索引0左侧的元素乘积。由于索引0是数组的第一个元素,其左侧没有任何元素,因此左侧元素的乘积应当是乘法的单位元,即1。这样初始化可以确保在后续计算中,索引0位置的输出正确表示除自身外其他元素的乘积。
🦆
为什么在计算过程中,需要从左到右和从右到左各遍历一次数组?能否通过一次遍历完成计算?
在计算过程中分两次遍历(从左到右和从右到左)是为了分别计算每个索引位置左侧和右侧的元素乘积。第一次遍历从左到右计算并存储每个位置左边所有元素的乘积。第二次遍历从右到左时,结合已存储的左侧乘积和动态计算的右侧乘积,得到最终的结果。通过这种方式,我们能够在不使用除法的情况下完成计算。理论上,通过一次遍历完成这种计算是不可行的,因为每个位置的计算需要依赖于其左侧和右侧所有元素的乘积,这两个信息在只遍历一次的情况下无法同时得到。
🦆
在从右到左遍历时,变量`R`是如何确保不会因为某些特殊值(如0)在`nums`数组中而导致计算错误?
变量`R`在从右到左遍历过程中仅用于累计当前索引右侧的元素乘积。如果`nums`数组中包含0,那么在遍历到0的位置时,`R`将被重置为0(因为乘以0的结果是0)。在继续向左遍历时,`R`将从新的非零值重新开始累计乘积。这种处理方式确保了即使遇到0,计算也能正确反映出,当一个索引位置的元素为0时,除该元素外的乘积应该为0(因为包含了该0元素的乘积)。
🦆
如果数组`nums`中包含零,题解的算法会如何处理?输出结果是否正确反映了除自身以外的乘积?
如果数组`nums`中包含零,算法在遍历过程中会在遇到0时使得乘积变为0。例如,如果某个位置`i`的元素是0,那么在从左到右的遍历中,所有i之后的位置的左侧乘积都会包含这个0,从而这些位置的乘积都为0。同理,在从右到左遍历时,i位置的右侧乘积也会为0。最终,除了索引i对应的输出为除0之外所有元素的乘积(如果其他位置也没有0,则为所有元素的乘积),其他位置的输出均为0。这确保了输出结果正确反映了除自身以外的乘积。

相关问题

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

 

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

 

提示:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

乘积最大子数组

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

 

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

 

提示:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

粉刷房子 II

粉刷房子 II