力扣最热一百题——除自身以外数组的乘积

目录

题目链接:238. 除自身以外数组的乘积 - 力扣(LeetCode)

题目描述

示例

提示:

解法一:左右数组(小型动态规划)

实现思路

Java写法:

运行时间

C++写法:

运行时间

时间复杂度以及空间复杂度

总结


题目链接:238. 除自身以外数组的乘积 - 力扣(LeetCode)

注:下述题目描述和示例均来自力扣

题目描述

给你一个整数数组 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) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)


解法一:左右数组(小型动态规划)

        这个问题可以通过两次遍历数组来解决,而不需要使用额外的空间(除了用于结果的数组之外),但这段代码巧妙地使用了两个辅助数组 left 和 right 来分别存储每个元素左侧所有元素的乘积和右侧所有元素的乘积,从而避免了在单次遍历中同时计算左右两侧乘积的复杂性。

实现思路

  1. 初始化
    • 首先,创建一个与输入数组 nums 长度相同的数组 left,用于存储每个元素左侧所有元素的乘积(包括元素本身位置为1的情况,因为元素本身不参与计算)。
    • 同时,创建一个与 nums 长度相同的数组 right,用于存储每个元素右侧所有元素的乘积(同样,元素本身位置为1)。
  2. 计算左侧乘积
    • 遍历 nums 数组,从左到右。
    • 对于 left 数组的每个位置 i,其值等于 nums[i-1](如果 i > 0)与 left[i-1] 的乘积。如果 i = 0,则 left[0] = 1,因为没有元素在 nums[0] 的左侧。
  3. 计算右侧乘积
    • 遍历 nums 数组,但这次是从右到左。
    • 对于 right 数组的每个位置 i,其值等于 nums[i+1](如果 i < len-1)与 right[i+1] 的乘积。如果 i = len-1,则 right[len-1] = 1,因为没有元素在 nums[len-1] 的右侧。
  4. 计算最终结果
    • 再次遍历 nums 数组,这次是为了计算每个元素的最终结果。
    • 对于 nums 数组的每个位置 i,其最终值等于 left[i](左侧所有元素的乘积)与 right[i](右侧所有元素的乘积)的乘积。
  5. 返回结果
    • 将修改后的 nums 数组返回,此时 nums 数组的每个元素都已经是除了它自身以外所有元素的乘积了。

Java写法:

class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;if(len == 0){return nums;}// 定义出两个数组分别表示左边的乘积和右边数组的乘积// 这个思路有点和动态规划相似//       0  1  2 3//       1, 2, 3,4// left  1, 1, 2,6// right 24,12,4,1int[] left = new int[len];int[] right = new int[len];// 填入左边乘积数组的值// 初始化left[0] = 1;for(int i = 1; i < len ; i++){left[i] = nums[i - 1] * left[i - 1];}// 填入右边乘积数组的值right[len - 1] = 1;for(int i = len - 2; i >= 0 ; i--){right[i] = nums[i + 1] * right[i + 1];}for(int i = 0; i < len; i++){nums[i] = left[i] * right[i];}return nums;}
}
运行时间

C++写法:

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int len = nums.size();vector<int> left(len);vector<int> right(len);left[0] = 1;for(int i = 1; i < len; i++){left[i] = nums[i - 1] * left[i - 1];}right[len - 1] = 1;for(int i = len - 2; i >= 0; i--){right[i] = nums[i + 1] * right[i + 1];}for(int i = 0; i < len; i++){nums[i] = left[i] * right[i];}return nums;}
};
运行时间

时间复杂度以及空间复杂度


总结

        累了哥几个,最近有点焦虑了,不总结了哎

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/146024.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

虚拟现实与PD协议快充

随着虚拟现实&#xff08;VR&#xff09;技术的不断进步&#xff0c;索尼的PlayStation VR2&#xff08;简称PS VR2&#xff09;凭借其卓越的性能和沉浸式体验&#xff0c;在游戏界引起了广泛关注。为了进一步拓展PS VR2的应用范围&#xff0c;索尼推出了PS VR2适配器&#xff…

IS-ISv4/6双栈

文章目录 IS-ISv4/6双栈实验要求配置 IS-ISv4/6双栈 实验要求 配置双栈 R1、2、3、4配置 IS-ISv4 和 IS-ISv6&#xff0c;配置IPv6多拓扑 上面为Level-1类型、中间为Level-1-2、下面是Level-2类型 还有就是说ATT位置1有一定要求连接L1/2连接L1或者L2类型路由器&#xff0c;至…

简单题94. 二叉树的中序遍历 (python)20240921

问题描述&#xff1a; #### python&#xff1a; # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution(…

统信服务器操作系统【搭建FTP】设置介绍

如何在操作系统上安装vsftp服务。设置匿名用户登录、设置授权用户密码访问功能,并介绍使用匿名方式、授权用户方式访问vsftp服务。本文适用于A、D、E三个服务器操作系统版本,除安装方式的差异,其他设置均相同。 文章目录 功能概述一、功能介绍二、准备环境三、安装步骤1. 在…

pg_start_backup

pg_start_backup()函数在主库上发起一个在线备份&#xff0c;命令执行成功后&#xff0c;将数据文件拷贝到备份接口中 select pg_start_backup(full0918,false,false); 以上会话不要关闭&#xff0c;复制数据目录。 cp -r /pgdata/data/postgres-f66f5f7a/ /opt/qfusion/mnt/st…

光伏开发:一分钟生成光伏项目报告

传统光伏项目报告的编制往往需要收集大量数据、进行复杂计算与分析&#xff0c;耗时长且易受人为因素影响。自动生成光伏项目报告&#xff0c;依托大数据、云计算、人工智能等先进信息技术&#xff0c;实现了对光伏项目关键参数的快速分析、评估与预测。 一、核心功能与流程 1…

Leetcode面试经典150题-39.组合总数

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如…

汇川AM400脉冲轴控制(轴控功能块ST源代码)

汇川AM400如何和编程软件通信连接 汇川AM400PLC如何和编程软件通信连接_汇川am400读取程序-CSDN博客文章浏览阅读159次。本文介绍了如何使用CODESYS编程软件与汇川AM400PLC进行通信连接,包括扫描网络、修改IP地址、刷新日志和下载监控程序的步骤。同时,文章提到了CODESYS编程…

python-3n+1数链/233

一&#xff1a;3n1数链题目描述 在计算机科学上&#xff0c;有很多类问题是无法解决的&#xff0c;我们称之为不可解决问题。然而&#xff0c;在很多情况下我们并不知道哪一类问题可以解决&#xff0c;哪一类问题不可解决。现在我们就有这样一个问题&#xff0c;问题如下&#…

DOG:知识图谱大模型问答的迭代交互式推理,克服长路径和假阳性关系挑战

DOG&#xff1a;知识图谱大模型问答的迭代交互式推理&#xff0c;克服长路径和假阳性关系挑战 秒懂大纲提出背景解法拆解全流程优化和医学关系 创意 秒懂大纲 ├── DoG框架【主题】 │ ├── 背景【研究背景】 │ │ ├── LLMs的局限性【问题描述】 │ │ │ …

go 读取excel

一、安装依赖 go get github.com/tealeg/xlsx二、main.go package mainimport "fmt" import "github.com/tealeg/xlsx"type Student struct {Name stringSex string }func (student Student) show() {fmt.Printf("Name:%s Sex:%s\r\n", stude…

消灭病毒gamedemo

DestoryVirus 一、AudioSourceManager using System.Collections; using System.Collections.Generic; using UnityEngine;public class AudioSourceManager : MonoBehaviour {public static AudioSourceManager Instance { get; private set; }public SoundPlayer soundPla…

JavaWeb初阶 day1

目录 tomcat目录结构 tomcat:web服务器软件 项目部署的方式 直接将项目放到webapps下 配置conf/server.xml文件 在conf\Catalina\localhost创建任意名称的xml文件。在文件中编写 静态项目和动态项目 Servlet Servlet执行原理 Servlet方法&#xff08;生命周期&#x…

Linux入门学习:make/Makefile(Linux项目自动化构建工具)

文章目录 1. makefile文件语法2. make clean工程清理3. 细节语法4. make原理 ⭕背景&#xff1a; 会不会写makefile&#xff0c;从一个侧面说明了一个人是否具备完成大型工程的能力。一个工程中的源文件不计数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c…

Linux相关概念和重要知识点(5)(权限的修改、时间属性)

1.权限的修改 &#xff08;1&#xff09;提权行为 普通用户是会受到权限的限制&#xff0c;但root账户无视一切权限限制&#xff0c;因此当我们要获取更高的权限&#xff0c;有一种办法就是将自己变成root或者短暂拥有和root一样的权力。 普通用户 -> root &#xff1a;s…

C++QT医院专家门诊预约管理系统

目录 一、项目介绍 二、项目展示 三、源码获取 一、项目介绍 医院专家门诊预约管理系统 [要求] 该系统需创建和管理以下信息&#xff1a;1、门诊专家信息&#xff1a;专家姓名、编号、性别、年龄、职称、门诊科目、服务时间、门诊预约数据集等&#xff1b;2、门诊预约信息…

2024 研究生数学建模竞赛(E题)建模秘籍|高速公路应急车道紧急启用模型|文章代码思路大全

铛铛&#xff01;小秘籍来咯&#xff01; 小秘籍团队独辟蹊径&#xff0c;运用聚类分析&#xff0c;逻辑回归模型&#xff0c;决策树/规则&#xff0c;ARIMA等强大工具&#xff0c;构建了这一题的详细解答哦&#xff01; 为大家量身打造创新解决方案。小秘籍团队&#xff0c;始…

Open3D 计算点云的曲率密度参数【2024最新版】

目录 一、算法原理1、曲率密度参数2、参考文献二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接,首发于:2024年9月21日。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的抄袭狗。 一、算法原理 1、曲率密度参数 对于点云数据集中任意一点 p i p_i

Python Selenium 自动化爬虫 + Charles Proxy 抓包

一、场景介绍 我们平常会遇到一些需要根据省、市、区查询信息的网站。 1、省市查询 比如这种&#xff0c;因为全国的省市比较多&#xff0c;手动查询工作量还是不小。 2、接口签名 有时候我们用python直接查询后台接口的话&#xff0c;会发现接口是加签名的。 而签名算法我…

vue3 TagInput 实现

效果 要实现类似于下面这种效果 大致原理 其实是很简单的,我们可以利用 element-plus 组件库里的 el-tag 组件来实现 这里我们可以将其抽离成一个公共的组件,那么现在有一个问题就是通讯问题 这里我们可以利用父子组件之间的通讯,利用 v-model 来实现,父组件传值,子组…