首页 > 其他分享 >力扣经典150题第十三题:除自身以外数组的乘积

力扣经典150题第十三题:除自身以外数组的乘积

时间:2024-04-10 09:59:09浏览次数:26  
标签:150 第十三 nums int 复杂度 力扣 数组 answer 乘积

目录

力扣经典150题第十三题:除自身以外数组的乘积

1. 简介

本文介绍如何设计一个算法,使用 O(n) 时间复杂度且不使用除法,计算数组 nums 中除自身以外所有元素的乘积。

2. 问题分析

给你一个整数数组 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]

提示:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶:你可以在 O(1) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)

3. 解题思路

方法一:左右乘积列表
  • 使用两个数组 leftright 分别记录每个元素左侧所有元素的乘积和右侧所有元素的乘积。
  • 最终结果 answer[i] 即为 left[i] * right[i]
方法二:优化空间复杂度
  • 使用一个数组 answer 作为输出结果。
  • 先遍历计算左侧所有元素的乘积,然后再遍历计算右侧所有元素的乘积,并将结果累积到 answer 中。

4. 代码实现

import java.util.*;

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        
        // 计算左侧所有元素的乘积
        int leftProduct = 1;
        for (int i = 0; i < n; i++) {
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }
        
        // 计算右侧所有元素的乘积,并累积到 answer 中
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return answer;
    }
}

5. 时间复杂度分析

  • 遍历数组两次,时间复杂度为 O(n)。

6. 应用和扩展

  • 该算法可以有效地解决数组乘积问题,且不使用除法,时间复杂度为 O(n)。
  • 可以通过优化空间复杂度进一步改进算法,使得空间复杂度达到 O(1)。

7. 总结

本文介绍了如何使用两种方法解决除自身以外数组的乘积问题,其中一种方法通过左右乘积列表实现,另一种方法优化了空间复杂度。该算法适用于需要在 O(n) 时间复杂度内解决数组乘积问题的场景。

8. 参考资料

标签:150,第十三,nums,int,复杂度,力扣,数组,answer,乘积
From: https://blog.csdn.net/weixin_44976692/article/details/137584329

相关文章

  • Offer必备算法23_两个数组dp_八道力扣题详解(由易到难)
    目录①力扣1143.最长公共子序列解析代码②力扣1035.不相交的线解析代码③力扣115.不同的子序列解析代码④力扣44.通配符匹配解析代码⑤力扣10.正则表达式匹配解析代码⑥力扣97.交错字符串解析代码⑦力扣712.两个字符串的最小ASCII删除和解析代码⑧力扣71......
  • 【每周例题】力扣 C++ 移除元素
    移除元素题目移除元素 思路分析1.涉及到容器,那么就很直接的想法,遍历容器,找出与val相同的数,移除,然后利用函数输出长度与移除后的数组2.移除部分我们使用指针去处理,用指针遍历数组,符合移除条件的利用erase函数移除注:这里使用到了一个万能头文件,参加蓝桥杯的同学可以试试运用......
  • 螺旋矩阵II(力扣59)
    给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 nxn 正方形矩阵 matrix 。示例1:输入:n=3输出:[[1,2,3],[8,9,4],[7,6,5]]示例2:输入:n=1输出:[[1]]提示:1<=n<=20解题思路:明白怎么循环输出,并且每次循环的边界在......
  • 交换量表节点(物理上,力扣24)
    题目如下:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]示例2:输入:head=[]输出:[]示例3:输入:head=[1]输出:[1]提示:链表中节点的......
  • 两个链表的交集(力扣349)
    题目如下:给定两个数组 nums1 和 nums2 ,返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例1:输入:nums1=[1,2,2,1],nums2=[2,2]输出:[2]示例2:输入:nums1=[4,9,5],nums2=[9,4,9,8,4]输出:[9,4]解释:[4......
  • 移除链表元素(虚拟节点法、力扣203)
    题目给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val==val 的节点,并返回 新的头节点 。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:head=[7,7,7,7],val=......
  • LeetCode 面试经典150题---003
    ####55.跳跃游戏给你一个非负整数数组nums,你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回true;否则,返回false。1<=nums.length<=1040<=nums[i]<=105本题题意比较明确,我们可以......
  • 混辗式混砂机 变速箱 旋耕灭茬机 污水处理 150T液压机 污水处理厂 饺子机 农村生活污
    UHT管式杀菌机说明书混辗式混砂机机械结构设计 论文CAD图纸开题报告毕业设计之专用机床图纸毕业设计推钢机液压图纸毕业设计3吨叉车3进3退变速箱(毕业设计)1G-160型旋耕灭茬机中央传动装置设计(共17张CAD加说明书与侧边传动装置配套污水处理课程设计图集150T液压机设计【10......
  • CS 1501KhattabGeneral警长提示
    CS1501KhattabGeneral警长提示•您可以使用ag.getAirports().size()获取顶点的数量,从而ag是一个AirlineGraph对象•使用for(Stringairport:ag.getAirports())在机场上迭代{…}•您可以使用ag.getAirportNo()方法•您可以使用检索机场的邻居集ag.adj(机场名称)•迭代邻居集:for(Router:a......
  • 链表--移除链表元素--力扣203
    目录题目思路代码细节题目给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val==val 的节点,并返回 新的头节点 。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:h......