问题描述
给定一个整数数组，要求返回一个新数组，新数组中的每个元素值是老数组中除了当前索引位置的其他元素的乘积。题目保证所有的乘积都在整形范围内。要求算法的时间复杂度为 O(n)，且求解过程中不能运用除法。题目链接：**点我**
样例输入输出
输入：[1,2,3,4]
输出：[24,12,8,6]
输入：[-1,1,0,-3,3]
输出：[0,0,9,0,0]
问题解法
此题参考：https://leetcode-cn.com/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/。主要是运用前缀和的算法，要计算除了当前元素的其他所有元素的值，可以将其拆成两部分：当前元素左边元素的乘积、当前元素右边元素的乘积，然后将这两个乘积相乘，就得到当前位置的结果。在计算当前元素左边元素的乘积可以运用前缀和的算法，计算当前元素右边元素的乘积也可以运用前缀和的算法（从末尾往前计算），只需要求出这两部分，然后对数组的每个位置的左前缀积和右后缀积进行相乘，就能得到整个数组的结果。
为了进一步优化空间，可以把左前缀积暂存在结果数组中，然后用一个变量存放右后缀积，计算过程中从末尾往前遍历，分别更新结果数组的值以及右后缀积的变量值。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
result[0] = 1;
for (int i = 1; i < nums.length; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
int suffixProduct = 1;
for (int i = nums.length - 1; i >= 0; i--) {
result[i] = result[i] * suffixProduct;
suffixProduct = suffixProduct * nums[i];
}
return result;
}
}
|
参考资料
https://leetcode-cn.com/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/