除自身以外数组的乘积
难度:
标签:
题目描述
给你一个整数数组 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是基于什么考虑?
▷🦆
为什么在计算过程中,需要从左到右和从右到左各遍历一次数组?能否通过一次遍历完成计算?
▷🦆
在从右到左遍历时,变量`R`是如何确保不会因为某些特殊值(如0)在`nums`数组中而导致计算错误?
▷🦆
如果数组`nums`中包含零,题解的算法会如何处理?输出结果是否正确反映了除自身以外的乘积?
▷相关问题
接雨水
给定 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