AlgoPressAppearance
0238-除自身以外数组的乘积
https://leetcode.cn/problems/product-of-array-except-self
给你一个长度为n的整数数组nums，其中n > 1，返回输出数组output，其中 output[i]等于nums中除nums[i]之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在O(n) 时间复杂度内完成此题。
进阶： 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
思路
暴力法：O(n^2),会超时,不符合提议 不能使用除法，所以不能全部相乘再除以自己 (测试用例中有0) O(n) 所以不能嵌套循环
思路2：前缀后缀法
我们定义 prefix 表示数字i前面的所有数字的乘积， suffix 表示数字i后面所有数字的乘积 那么 output[i] = prefix[i] * suffix[i] 我们可以循环两次，将 prefix 和 suffix 的值算出
参考代码
csharp
public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;
int[] prefix = new int[n];
int[] suffix = new int[n];
int[] output = new int[n];
prefix[0] = 1;
for(int i=1; i<n; i++){
prefix[i] = prefix[i-1] * nums[i-1];
}
suffix[n-1] =1;
for(int i=n-2; i>=0; i--){
suffix[i] = suffix[i+1] * nums[i+1];
}
for(int i=0; i<n; i++){
output[i] = prefix[i] * suffix[i];
}
return output;
}
}
思路：优化空间
上述 prefix 和 suffix 都定义了 O(n) 的数组 如果我们只定义这两个变量，然后循环的时候，保持 prefix/suffix 不停的和当前的数相乘。 那么我们可以一直得到对应的 prefix 的 suffix，因为 output 是需要 i 之前的结果，所以我们先计算 output 在计算 prefix 和 suffix 最后将两个循环合并到一起啊，prefix从前往后计算, suffix 从后往前计算
参考代码
csharp
public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;
int[] output = new int[n];
int prefix = 1;
int suffix = 1;
//output置为1
for(int i=0; i<n; i++){
output[i] = 1;
}
for(int i=0; i<n; i++){
//先计算 output
output[i] *= prefix;
output[n-1-i] *= suffix;
//再计算响应的 prefix/suffix
prefix *= nums[i];
suffix *= nums[n-1-i];
}
return output;
}
}
复习:20220615
csharp
public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;
int[] result = new int[n];
Array.Fill(result,1);
int prefix = 1;
for(int i=0; i<n; i++){
result[i]*=prefix;
prefix*=nums[i];
}
int suffix = 1;
for(int i=n-1;i>=0;i--){
result[i]*=suffix;
suffix*=nums[i];
}
return result;
}
}