力扣 - 剑指 Offer 66. 构建乘积数组
2021/11/4 6:11:45
本文主要是介绍力扣 - 剑指 Offer 66. 构建乘积数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 66. 构建乘积数组
思路1
-
按照一般的思路就是将所有的相乘,然后除以每一位数字就是答案,但是题目要求我们不能使用除法,因此我们会想到每次遍历到每个数字的时候,在遍历一遍数组,将除开自己以外的数字相乘,但是这样做的时间复杂度确是\(O(N^2)\),导致超时,因此我们需要想另外一种方法来解决
-
根据题意,我们可以知道
B[i]=A[0]*A[1]*A[2]*...*A[i-1]*A[i+1]*...*A[n-1]
,所以我们以i
为分界线,将这个拆成两部分,所以B[i]
就等于A[0]*...*A[i-1]
与A[i+1]*...*A[n-1]
的乘积,所以数组B可以看作用一个矩阵来创建。我们以[1, 2, 3, 4]
为例,如图所示:可以看出,对角线是都为1。然后从第二行开始,我们先计算下三角的每一行的乘积:
B[i] = B[i-1] * A[i-1]
从倒数第二行开始,再从下往上计算上结果:
B[i] *= A[i+1]
,因为左边部分已经计算出来了,所以直接拿来乘就可以了
代码
class Solution { public int[] constructArr(int[] a) { int length = a.length; if (length == 0) { return new int[0]; } int[] arr = new int[length]; // 先构建左下三角形 arr[0] = 1; for (int i = 1; i < length; i++) { arr[i] = arr[i-1] * a[i-1]; } // 构建右上三角形同时计算结果 int temp = 1; // 从倒数第二个开始往前 for (int i = length-2; i >= 0; i--) { temp *= a[i+1]; arr[i] *= temp; } return arr; } }
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(1)\)
这篇关于力扣 - 剑指 Offer 66. 构建乘积数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统