当前位置: 首页 > news >正文

LeetCode热题100- 缺失的第一个正数【JavaScript讲解】

题目:在这里插入图片描述

解题一:

如果不考虑时间复杂度和空间复杂度的话,我们最先想到的办法是先将该数组进行排序和去重,将最初的res结果值设置为1;将然后进行遍历,如果第一项不为1,则返回1,否则根据遍历res++;遍历结束后发现每一项都符合要求则返回res的最终值。代码如下:

代码一:

/*** @param {number[]} nums* @return {number}*/
var firstMissingPositive = function(nums) {nums = Array.from(new Set(nums));nums.sort((a,b)=>a-b);let res = 1;for(let i = 0; i < nums.length;i++){if(nums[i] > 0){if(nums[i] != res){return res;}res++;}}return res;
};

‌sort函数的时间复杂度为O(n log n),空间复杂度为O(n)
‌new Set操作的时间复杂度是O(n),空间复杂度也是O(n)‌
以上代码并没有满足题目要求的时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

解题二:

我们这次使用了一个Set(numSet)来存储数组中出现过的正数。首先,我们遍历原数组nums,将每个在1到n范围内的正数添加到Set中。然后,我们再次遍历从1到n的每个数字,检查它是否在Set中出现过。如果找到一个没有出现过的数字,我们就返回它作为缺失的第一个正整数。如果所有1到n的数字都出现过,我们则返回n+1。

代码二:

/*** @param {number[]} nums* @return {number}*/
var firstMissingPositive = function(nums) {let numSet = new Set();let n = nums.length;for(let i = 0; i < n;i++){if(nums[i] > 0 && nums[i] <= n){numSet.add(nums[i]);}}for(let i = 1; i <= n;i++){if(!numSet.has(i)){return i;}}return n + 1;
};

但是我们使用了一个额外的Set来存储出现过的数字,所以这里的空间复杂度为O(n);时间复杂度是O(n),因为我们只遍历了数组两次,并且Set的查找和插入操作都是O(1)的。

解题三:

将所有负数、0 都变为 N + 1,我们只需要考虑1-n的数字
遍历每个数,如果该数 |x| 属于[1,N];把在 x-1 的位置的数加上一个负号
遍历完之后,如果全部数都是负数——答案就是 1+N,否则就是第一个正数的位置+1

代码三:

/*** @param {number[]} nums* @return {number}*/
var firstMissingPositive = function(nums) {let n = nums.length;for(let i = 0; i < n;i++){if(nums[i] <= 0) nums[i] = n + 1;}for(let i = 0; i < n;i++){let x = Math.abs(nums[i]);if(x >= 1 && x <= n){nums[x - 1] = nums[x - 1] < 0 ? nums[x - 1] : -nums[x - 1];}}for(let i = 0; i < n;i++){if(nums[i] >= 0) return i+1;}return n + 1;
};

此时就满足时间复杂度为o(n),空间复杂度为常数的代码了。此思路借鉴于力扣博主okkjoo,具体地址点击此处跳转。

当博主问朋友解决方案的时候,他二话不说的告诉我“用桶排啊!!”,于是,、、、、这篇文章到这里没有结束,,明天博主会尽快将桶排的方法补充上去,也欢迎小伙伴们在评论区留下你们的答案哦~~~~~

相关文章:

LeetCode热题100- 缺失的第一个正数【JavaScript讲解】

题目&#xff1a; 解题一&#xff1a; 如果不考虑时间复杂度和空间复杂度的话&#xff0c;我们最先想到的办法是先将该数组进行排序和去重&#xff0c;将最初的res结果值设置为1&#xff1b;将然后进行遍历&#xff0c;如果第一项不为1&#xff0c;则返回1&#xff0c;否则根…...

JAVA泛型介绍与举例

Java中&#xff0c;泛型用于编译阶段限制集合中元素的类型&#xff0c;或者限制类中某个属性的类型&#xff0c;编译过程中发生类型擦除&#xff0c;最终还是Object类型。 1. 集合中的泛型 集合默认可以存储任何类型的元素&#xff0c;即Object类型&#xff0c;当使用一个集合…...

【ISO 14229-1:2023 UDS诊断(会话控制0x10服务)测试用例CAPL代码全解析③】

ISO 14229-1:2023 UDS诊断【会话控制0x10服务】_TestCase03 作者&#xff1a;车端域控测试工程师 更新日期&#xff1a;2025年02月15日 关键词&#xff1a;UDS诊断、0x10服务、诊断会话控制、ECU测试、ISO 14229-1:2023 TC10-003测试用例 用例ID测试场景验证要点参考条款预期…...

Vivado生成edif网表及其使用

介绍如何在Vivado中将模块设为顶层&#xff0c;并生成相应的网表文件&#xff08;Verilog文件和edif文件&#xff09;&#xff0c;该过程适用于需要将一个模块作为顶层设计进行综合&#xff0c;并生成用于其他工程中的网表文件的情况。 例如要将fpga_top模块制作成网表给其它工…...

Win10环境借助DockerDesktop部署大数据时序数据库Apache Druid

Win10环境借助DockerDesktop部署最新版大数据时序数据库Apache Druid32.0.0 前言 大数据分析中&#xff0c;有一种常见的场景&#xff0c;那就是时序数据&#xff0c;简言之&#xff0c;数据一旦产生绝对不会修改&#xff0c;随着时间流逝&#xff0c;每个时间点都会有个新的…...

mac 意外退出移动硬盘后再次插入移动硬盘不显示怎么办

第一步&#xff1a;sudo ps aux | grep fsck 打开mac控制台输入如下指令&#xff0c;我们看到会出现两个进程&#xff0c;看进程是root的这个 sudo ps aux|grep fsck 第二步&#xff1a;杀死进程 在第一步基础上我们知道不显示u盘的进程是&#xff1a;62319&#xff0c;我们…...

力扣动态规划-32【算法学习day.126】

前言 ###我做这类文章一个重要的目的还是记录自己的学习过程&#xff0c;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非常非常高滴&#xff01;&#xff01;&#xff01; 习题 1.完全平方数 题目链接:279. 完全…...

【算法进阶详解 第一节】树状数组

【算法进阶详解 第一节】树状数组 前言树状数组基础树状数组原理树状数组能够解决的问题 树状数组提高树状数组区间加&#xff0c;区间和操作二维树状数组 树状数组应用树状数组区间数颜色树状数组二维偏序 前言 树状数组在算法竞赛中十分常见&#xff0c;其能解决二维数点&am…...

【苍穹外卖】学习

软件开发整体介绍 作为一名软件开发工程师,我们需要了解在软件开发过程中的开发流程&#xff0c; 以及软件开发过程中涉及到的岗位角色&#xff0c;角色的分工、职责&#xff0c; 并了解软件开发中涉及到的三种软件环境。那么这一小节&#xff0c;我们将从 软件开发流程、角色…...

Python常见面试题的详解8

1. 变量作用域和查找规则&#xff08;LEGB&#xff09; 作用域层级&#xff1a; Local&#xff1a;函数内部作用域 Enclosing&#xff1a;闭包函数外层作用域 Global&#xff1a;模块全局作用域 Built-in&#xff1a;内置命名空间 查找顺序&#xff1a;L → E → G → B关…...

Deepseek R1模型本地化部署与API实战指南:释放企业级AI生产力

摘要 本文深入解析Deepseek R1开源大模型的本地化部署流程与API集成方案&#xff0c;涵盖从硬件选型、Docker环境搭建到模型微调及RESTful接口封装的完整企业级解决方案。通过电商评论分析和智能客服搭建等案例&#xff0c;展示如何将前沿AI技术转化为实际生产力。教程支持Lin…...

node.js + html调用ChatGPTApi实现Ai网站demo(带源码)

文章目录 前言一、demo演示二、node.js 使用步骤1.引入库2.引入包 前端HTML调用接口和UI所有文件总结 前言 关注博主&#xff0c;学习每天一个小demo 今天是Ai对话网站 又到了每天一个小demo的时候咯&#xff0c;前面我写了多人实时对话demo、和视频转换demo&#xff0c;今天…...

sql语言语法的学习

sql通用语法 sql分类 DDL(操作数据库和表) 操作数据库 操作表_查询 操作表_创建 举例&#xff1a; 操作表_删除 操作表_修改 DML(增删改表中数据) DML添加数据 DML删除数据 DML修改数据 DQL 单表查询 基础查询 条件查询 案例演示&#xff1a; 排序查询 聚合函数 分组查询…...

力扣 最长递增子序列

动态规划&#xff0c;二分查找。 题目 由题&#xff0c;从数组中找一个最长子序列&#xff0c;不难想到&#xff0c;当这个子序列递增子序列的数越接近时是越容易拉长的。从dp上看&#xff0c;当遍历到这个数&#xff0c;会从前面的dp选一个最大的数加上当前数&#xff0c;注意…...

【linux】在 Linux 服务器上部署 DeepSeek-r1:70b 并通过 Windows 远程可视化使用

【linux】在 Linux 服务器上部署 DeepSeek-r1:70b 并通过 Windows 远程可视化使用 【承接商业广告,如需商业合作请+v17740568442】 文章目录 【linux】在 Linux 服务器上部署 DeepSeek-r1:70b 并通过 Windows 远程可视化使用个人配置详情一、安装ollama二、下载deepseek版本…...

visutal studio 2022使用qcustomplot基础教程

编译 下载&#xff0c;2.1.1版支持到Qt6.4 。 拷贝qcustomplot.h和qcustomplot.cpp到项目源目录&#xff08;Qt project&#xff09;。 在msvc中将它俩加入项目中。 使用Qt6.8&#xff0c;需要修改两处代码&#xff1a; L6779 # if QT_VERSION > QT_VERSION_CHECK(5, 2, …...

Linux:线程概念、理解、控制

目录 一、认识线程 1.认识线程V1 2.认识线程V2 3.认识线程V3 4.认识线程V4 5.认识线程V5 二、线程控制 1.前言 2.创建线程 3.线程等待 4.线程终止 5.线程分离 三、线程理解 一、认识线程 1.认识线程V1 借用大多数计算机教材的话&#xff0c;线程是进程的一个执行…...

Postman如何流畅使用DeepSeek

上次写了一篇文章是用chatBox调用api的方式使用DeepSeek&#xff0c;但是实际只能请求少数几次就不再能给回响应。这回我干脆用最原生的方法Postman调用接口请求好了。 1. 通过下载安装Postman软件 postman下载(https://pan.quark.cn/s/c8d1c7d526f3)&#xff0c;包含7.0和10…...

K8S下载离线安装包所需文件

下载相关文件 官网下载地址集合https://kubernetes.io/zh-cn/releases/download/ 下载相关镜像 官网镜像描述 所有 Kubernetes 容器镜像都被部署到 registry.k8s.io 容器镜像仓库。 容器镜像支持架构registry.k8s.io/kube-apiserver:v1.32.0amd64, arm, arm64, ppc64le, …...

探索Hugging Face:开源AI社区的核心工具与应用实践

引言&#xff1a;AI民主化的先锋 在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;Hugging Face已成为开源社区的代名词。这个成立于2016年的平台&#xff0c;通过提供易用的工具和丰富的预训练模型库&#xff0c;彻底改变了开发者使用和部署AI模型的方式。截至202…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...