小庄同学

V1

2022/06/15阅读:22主题:橙心

(云上)剑指 Offer 66. 构建乘积数组

Hi,大家好,我是小庄。

今天打卡的算法题是 —— 剑指 Offer 66. 构建乘积数组。

话不多说,一起来学习吧~

一、Leetcode题目

1、题目地址

点击查看Leetcode题目

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。

三、参考文档

链接:https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
作者: Krahets

分类:

前端

标签:

前端

作者介绍

小庄同学
V1

富途-前端开发