238. 除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法,且在 O(n) 时间复杂度内完成此题。
这题乍一看很简单,但是,这题有两个条件, 不能用除法,时间复杂度O(n)。这样把最自然想到的两种解法都排除了。
官方解法
思路 answer[i]等于 它左边所有数的乘积 与 它右边所有数乘积 的积。
想到这一点就不用两层循环去求了,可以一层循环解决。
这个思路最直观的解法是左边的积和右边的积都定义一个数组,官方给的优化解法就是右边的数组再循环中一次一次的计算,就少定义一个数组。加上题目特意说的 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。 就达到了O(1)的空间复杂度。
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] answer = new int[length];
// answer[i] 表示索引 i 左侧所有元素的乘积
// 因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1
answer[0] = 1;
for (int i = 1; i < length; i++) {
answer[i] = nums[i - 1] * answer[i - 1];
}
// R 为右侧所有元素的乘积
// 刚开始右边没有元素,所以 R = 1
int R = 1;
for (int i = length - 1; i >= 0; i--) {
// 对于索引 i,左边的乘积为 answer[i],右边的乘积为 R
answer[i] = answer[i] * R;
// R 需要包含右边所有的乘积,所以计算下一个结果时需要将当前值乘到 R 上
R *= nums[i];
}
return answer;
}
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/product-of-array-except-self/solutions/272369/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。