面试经典150——除自身以外数组的乘积

本文主要是介绍面试经典150——除自身以外数组的乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源

力扣每日一题；题序：238

我的题解

方法一 前后缀乘积

分别计算前缀乘积L和后缀乘积R，分别表示位置i之前的乘积和位置i之后的乘积。对应位置i上的最终乘积就是L[i]*R[i]。
具体操作：

• 初始化L[0]=1,R[n-1]=1
• L[i]=L[i-1]*nums[i-1]
• R[i]=R[i+1]*nums[i+1]

时间复杂度：O(n)
空间复杂度：O(n)

public int[] productExceptSelf(int[] nums) {int n=nums.length;int[] L=new int[n];int[] R=new int[n];L[0]=1;R[n-1]=1;for(int i=1;i<n;i++)L[i]=L[i-1]*nums[i-1];for(int i=n-2;i>=0;i--)R[i]=R[i+1]*nums[i+1];for(int i=0;i<n;i++)L[i]=L[i]*R[i];return L;
}

方法二 优化空间版本

在方法一中如果除了将L作为结果输出数组，还需要一个额外的后缀乘积数组R，因此导致空间为O(n)，但是实际上R可以动态构建，不用暂存。

时间复杂度：O(n)
空间复杂度：O(1)

public int[] productExceptSelf(int[] nums) {int n=nums.length;int[] L=new int[n];int R=1;L[0]=1;for(int i=1;i<n;i++)L[i]=L[i-1]*nums[i-1];for(int i=n-1;i>=0;i--){L[i]=L[i]*R;R=R*nums[i];}return L;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

这篇关于面试经典150——除自身以外数组的乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---