13.除自身以外数组的乘积
题目
给你一个整数数组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
- 输入 保证 数组 answer[i] 在 32 位 整数范围内
思路
先计算数组中所有元素的乘积，然后将总的乘积除以数组的中每个元素x就是除自身值以外数组的乘积。
但是这样有个问题，如果数组中有一个元素是0，那这个方法就失效了，而且题目中说了不能使用除法运算。
我们可以分解为两部分：
- 得到索引左侧所有数字的乘积L
- 得到索引右侧所有数字的乘积R
- 两部分相乘
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
// L 和 R 分别表示左右两侧的乘积列表
int[] L = new int[length];
int[] R = new int[length];
int[] answer = new int[length];
// L[i] 为索引 i 左侧所有元素的乘积
// 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
L[0] = 1;
for (int i = 1; i < length; i++) {
L[i] = nums[i - 1] * L[i - 1];
}
// R[i] 为索引 i 右侧所有元素的乘积
// 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
R[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
R[i] = nums[i + 1] * R[i + 1];
}
// 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
for (int i = 0; i < length; i++) {
answer[i] = L[i] * R[i];
}
return answer;
}
}
复杂度分析:
- 时间复杂度：O(N)，其中 N 指的是数组 nums 的大小。预处理 L 和 R 数组以及最后的遍历计算都是 O(N) 的时间复杂度。
- 空间复杂度：O(N)，其中 N 指的是数组 nums 的大小。使用了 L 和 R 数组去构造答案，L 和 R 数组的长度为数组 nums 的大小。
尽管上面的方法已经能够很好的解决这个问题，但是空间复杂度并不为常数。
- 由于输出数组不算在空间复杂度内，那么我们可以将 L 或 R 数组用输出数组来计算。也就是不再新申请L和R数组，而只是用一个变量记录索引右侧元素的乘积之和。
- 第一遍遍历的时候将answer数组的值都填充为索引左侧元素的值(也就是上面方法中L的值)
- 再一次后续遍历的时候取answer中的值和数组索引右侧元素乘积的和值相乘并赋值到answer中。这个时候answer中的值就已经是乘积的和值了。
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
//初始化ans都为1
for (int i = 0; i < n; i++) {
ans[i] = 1;
}
//左侧
int L = 1;
for(int i = 0; i < n; i++){
ans[i] *= L;
L *= nums[i];
}
//右侧
int R = 1;
for(int i = n - 1; i >= 0; i--){
ans[i] *= R;
R *= nums[i];
}
return ans;
}
}
- 邮箱 ：charon.chui@gmail.com
- Good Luck!