剑指 Offer 66. 构建乘积数组
Hi,大家好,我是小庄。
今天打卡的算法题是 —— 剑指 Offer 66. 构建乘积数组。
话不多说,一起来学习吧~
一、题目
1、题目地址
2、具体题目
二、实现代码
1、思路:暴力破解法,超时;
(1)具体代码
/** * @param {number[]} a * @return {number[]} */ /* 方法:暴力破解***超时; 时间复杂度:O(n^2); 时间复杂度:O(n^2); */ function getNum(a, i) { let num = 1; for(let j=0; j<a.length; j++) { if(j !== i) { num *= a[j]; } } return num; } var constructArr = function(a) { let result = []; for(let i=0; i<a.length; i++) { result.push(getNum(a, i)); } return result; };
(2)运行结果
如下,最后输入的是极端案例:
2、(推荐)方法:下三角的乘积 * 上三角的乘积;
(1)具体代码
/** * @param {number[]} a * @return {number[]} */ /* 方法:下三角的乘积 * 上三角的乘积; 时间复杂度:O(N) 空间复杂度:O(N) */ var constructArr = function(a) { let len = a.length; // 1、排除数组为空的特殊情况; if (len === 0) { return []; } // 声明长度和len一样的数组b,且初始化b[0]=1, 中间变量temp=1; let b = new Array(len); b[0] = 1; let temp = 1; // 2、计算下三角形的乘积值,注意i从下标为1开始即可; for (let i=1; i<len; i++) { b[i] = b[i-1] * a[i-1]; } // 3、计算上三角形的乘积值,注意i从下标为len-2开始即可; for (let i=len-2; i>=0; i--) { temp *= a[i+1]; // 4、b[i] = 下三角乘积值 * 上三角乘积值; b[i] *= temp; } //4、返回数组b return b; };
(2)运行结果
(3)具体思路
(1) 初始化:数组 B ,其中 B[0] = 1;辅助变量 temp = 1;
(2) 计算 B[i]的下三角各元素的乘积,直接乘入 B[i] ;
(3) 计算 B[i]的上三角各元素的乘积,记为temp ,并乘入 B[i] ;
(4) 返回最后结果,即数组B。
#前端##算法工程师#公zhong号:深漂程序员小庄,专注于分享编码经验、技术干货、面试经验、偶尔分享深漂日常、工作书籍、实用书籍等。