当前位置:   article > 正文

力扣热门100题之除自身意外数组的成绩【中等】

力扣热门100题之除自身意外数组的成绩【中等】

题目描述

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法,且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:

在这里插入图片描述


解法1 总积法

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let multRes=1;
    let isZero=false;
    nums.forEach((v)=>{
        if(v!=0){
            multRes*=v;
        }else{
            isZero=true;
        }
    })
    let res=[]
    if(isZero){
        for(let i=0;i<nums.length;i++){
            if(nums[i]==0){
                nums[i]=1
                if(nums.indexOf(0)!=-1){
                    res.push(0);
                }else{
                    res.push(multRes);
                }
                nums[i]=0;
            }else{
                res.push(0);
            }
        }
    }else{ 
        nums.forEach((v)=>{
            res.push(multRes/v);
        })
    }
    return res;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

执行结果
在这里插入图片描述

解法2 左右乘积列表

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let l=[1]
    let r=[]
    r[nums.length-1]=1
    const len=nums.length;
    for(let i=1;i<len;i++){
        l[i]=l[i-1]*nums[i-1];
        r[len-1-i]=r[len-i]*nums[len-i]
    }
    let res=[]
    for(let i=0;i<len;i++){
        res[i]=l[i]*r[i]
    }
    return res;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

执行结果:
在这里插入图片描述

左右乘积列表优化

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let l=[1] //l[i] 表示i左侧所有元素的乘积
    const len=nums.length;
    let r=1;//r为左侧的乘积
    for(let i=1;i<len;i++){
        l[i]=l[i-1]*nums[i-1];
    }
    for(let i=len-1;i>=0;i--){
        l[i]=l[i]*r;
        r*=nums[i];
    }
   
    return l;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

执行结果:
在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/623338
推荐阅读
相关标签
  

闽ICP备14008679号