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

力扣每日一题41:缺失的第一个正数

题目描述:

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1:

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

示例 2:

输入:nums = [3,4,-1,1]
输出:2

示例 3:

输入:nums = [7,8,9,11,12]
输出:1

提示:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

通过次数

325.7K

提交次数

749K

通过率

43.5%

思路和题解:

设数组长度为n,则确实的第一个正数只能在[1,n+1]的闭区间

思路一:暴力搜索。时间O(n^2),空间O(1),不符合要求

依次判断[1,n]在不在数组里,如果不在就返回那个不在的数,如果都在就返回n+1。代码。

//暴力循环
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n=nums.size();for(int i=1;i<=n;i++){bool flag=false;for(int j=0;j<n;j++){if(nums[j]==i){flag=true;break;}}if(!flag) return i;}return n+1;}
};

思路二:普通的哈希表。时间O(n),空间O(n),不符合要求。

用一个长度为n的数组来标记[1,n]有没有出现过。

//普通哈希表
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n=nums.size();vector<bool> hash(n,false);for(int i=0;i<n;i++){//出现了就标记为真if(nums[i]>0&&nums[i]<=n)hash[nums[i]-1]=true;}for(int i=0;i<n;i++){if(hash[i]==false) return i+1;}return n+1;}
};

思路三:原地哈希表。时间O(n),空间O(1)

思路二是我们能想到的比较好的办法了,但是空间复杂度还是不能达到要求,那我们怎么来优化这个空间复杂度O(n)呢?要知道,只用O(n)的时间复杂度,也就是只用一层的循环,要找出缺失的第一个正数的话,不用其他空间来存储正数存在的状态时不可能的。既然必须要用空间来存储一些状态,又只能额外使用常数的空间,那我们只好拿给定的数组nums作为存储状态的空间。也就是说用原数组nums作为哈希表。

问题是怎么标记一个正数是否出现的状态。对于num<=0&&num>n的数,num在[1,n]之外无论怎么变化,都不会改变答案。那就干脆先把数组里所有<=0的数先变成n+1,之后再遍历数组,把每个[1,n]内的数num对应下标处都改为负数。最后再遍历一遍数组,对应元素不为负就说明这个数对应的位置是第一个缺失的正数。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {//原地哈希表//第一个缺失的数只能出现在[1,n+1]的闭区间里int n=nums.size();for(int i=0;i<n;i++){//若出现负数或零或大于n的数,那第一个确实的数就在[1,n]if(nums[i]<=0) nums[i]=n+1;}for(int i=0;i<n;i++){//将[num-1]标记为负,表示正数num没有缺失,num>n时不用管int num=abs(nums[i]);if(num<=n){nums[num-1]=-abs(nums[num-1]);}}for(int i=0;i<n;i++){if(nums[i]>0) return i+1;}return n+1;}
};

相关文章:

力扣每日一题41:缺失的第一个正数

题目描述&#xff1a; 给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,0] 输出&#xff1a;3示例 2&#xff1a; 输…...

OpenCV与mediapipe实践

1. 安装前准备 开发环境&#xff1a;vscode venv 设置vscode, 建立项目&#xff0c;如: t1/src, 用vscode打开&#xff0c;新建终端Terminal&#xff0c;这时可能会有错误产生&#xff0c;解决办法&#xff1a; 运行命令&#xff1a;Set-ExecutionPolicy -ExecutionPolicy …...

【css拾遗】粘性布局实现有滚动条的情况下,按钮固定在页面底部展示

效果&#xff1a; 滚动条滚动过程中&#xff0c;按钮的位置位于手机的底部 滚动条滚到底部时&#xff0c;按钮的位置正常 这个position:sticky真的好用&#xff0c;我原先的想法是利用滚动条滚动事件去控制&#xff0c;没想到css就可以解决 <template><view class…...

git 创建并配置 GitHub 连接密钥

前记&#xff1a; git svn sourcetree gitee github gitlab gitblit gitbucket gitolite gogs 版本控制 | 仓库管理 ---- 系列工程笔记. Platform&#xff1a;Windows 10 Git version&#xff1a;git version 2.32.0.windows.1 Function&#xff1a; git 创建并配置 GitHub…...

使用Premiere、PhotoShop和Audition做视频特效

今天接到一个做视频的任务&#xff0c;给一个精忠报国的视频&#xff0c;要求&#xff1a;   ①去掉人声&#xff0c;就是将唱歌的人声去掉&#xff0c;只留下伴奏&#xff1b;   ②截图视频中的横幅&#xff0c;做一个展开的效果&#xff0c;类似卷纸慢慢展开&#xff1b;…...

vueday01——动态参数

我们现在知道了 v-bind:的语法糖是: v-on:的语法糖是 我们现在来尝试一下&#xff0c;定义一个动态参数模拟点击事件按钮 <div :id"idValue" ref"myDiv">我是待测div{{ resultId }}</div> <button v-on:[eventName]"doSomething&…...

双向链表C语言版本

1、声明链表节点操作函数 linklist.h #ifndef LINKLIST_H__ #define LINKLIST_H__ #include <stdio.h> #include <stdlib.h> #include <stdbool.h>//#define TAIL_ADD #define HEAD_ADD typedef int LinkDataType; // 构造节点 struct LinkNode {LinkDataTy…...

visual studio安装时候修改共享组件、工具和SDK路径方法

安装了VsStudio后,如果自己修改了Shared路径&#xff0c;当卸载旧版本&#xff0c;需要安装新版本时发现&#xff0c;之前的Shared路径无法进行修改&#xff0c;这就很坑爹了&#xff0c;因为我运行flutter程序的时候&#xff0c;报错找不到windows sdk的位置&#xff0c;所以我…...

Motorola IPMC761 使用边缘TPU加速神经网络

Motorola IPMC761 使用边缘TPU加速神经网络 人工智能(AI)和机器学习(ML)正在塑造和推进复杂的自动化技术解决方案。将这些功能集成到硬件中&#xff0c;解决方案可以识别图像中的对象&#xff0c;分析和检测模式中的异常或找到关键短语。这些功能对于包括但不限于自动驾驶汽车…...

EM@直线的参数方程

文章目录 abstract直线参数方程从运动轨迹的角度从普通方程转换导参数方程向量法 参数方程间的转换从第3型转化为第2型方程组例 abstract 平面直线的参数方程的3种表示形式直线参数方程间的转换 直线参数方程 以下从不同角度推导直线参数方程分别记为第1,2,3形式参数方程 从…...

day08-注册功能、前端登录注册页面复制、前端登录功能、前端注册功能

1 注册功能 补充(开放文件夹内) 2 前端登录注册页面复制 4 前端注册功能 1 注册功能 # 分析前端&#xff1a;携带数据格式 {mobile:,code:,password}后端&#xff1a;-1 视图类---》注册方法-2 序列化类---》校验&#xff0c;保存&#xff08;表中字段多&#xff0c;传的少---…...

rust: function

///file: nestd.rs ///ide: RustRover 233.8264.22 /// /// /// /***自定义函数*/ pub fn function() {println!("called my::nested::function()"); }#[allow(dead_code)] fn private_function() {println!("called my::nested::private_function()"); }/…...

零代码编程:用ChatGPT批量下载谷歌podcast上的播客音频

谷歌podcast有很多播客音频&#xff0c;如何批量下载到电脑呢&#xff1f; 以这个播客为例&#xff1a; https://podcasts.google.com/feed/aHR0cHM6Ly9oYWRhcnNoZW1lc2guY29tL2ZlZWQvcG9kY2FzdC8?saX&ved0CAkQlvsGahcKEwi4uauWsvKBAxUAAAAAHQAAAAAQAg 查看网页源代码&a…...

nginx.4——正向代理和反向代理(七层代理和四层代理)

1、正向代理反向代理 nginx当中有两种代理方式 七层代理(http协议) 四层代理(tcp/udp流量转发) 七层代理 七层代理&#xff1a;代理的是http的请求和响应。 客户端请求代理服务器&#xff0c;由代理服务器转发给客户端http请求。转发到内部服务器&#xff08;可以单台&#…...

基于RuoYi-Flowable-Plus的若依ruoyi-nbcio支持自定义业务表单流程(三)

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 相应的后端也要做一些调整 1、启动流程修改如下&#xff1a; /*** 启动流程实例*/private R startProce…...

Spring-事务源码解析2

上一篇文章我们介绍了事务开启注解EnableTransactionManagement源码解析《Spring-事务源码解析1》 里面提到了2个关键组件&#xff0c;这里我们分析下Spring如何利用这2个组件来给Bean创建代理对象。 本篇文章我们看下当一个类里面包含了Transactional注解&#xff0c;Spring如…...

基于ssm008医院门诊挂号系统+jsp【附PPT|开题|任务书|万字文档(LW)和搭建文档】

主要功能 后台登录&#xff1a;4个角色 管理员&#xff1a; ①个人中心、修改密码、个人信息 ②药房管理、护士管理、医生管理、病人信息管理、科室信息管理、挂号管理、诊断信息管理、病例库管理、开药信息管理、药品信息管理、收费信息管理 药房&#xff1a; ①个人中心、修…...

【Linux常用命令11】Linux文件与权限详解

权限 r &#xff1a;读权限&#xff0c;用数字4表示 w &#xff1a;写权限&#xff0c;用数字2表示 x &#xff1a;执行权限&#xff0c;用数字1表示 常用权限 644&#xff1a;代表所有者拥有读、写权限&#xff0c;而所属组和其他人拥有只读权限。 755&#xff1a;代表所有…...

BAT026:删除当前目录指定文件夹以外的文件夹

引言&#xff1a;编写批处理程序&#xff0c;实现删除当前目录指定文件夹以外的文件夹。 一、新建Windows批处理文件 参考博客&#xff1a; CSDNhttps://mp.csdn.net/mp_blog/creation/editor/132137544 二、写入批处理代码 1.右键新建的批处理文件&#xff0c;点击【编辑】…...

Python浏览器自动化

如果你正在进行手机爬虫的工作&#xff0c;并且希望通过模拟浏览器行为来抓取数据&#xff0c;那么Pyppeteer将会是你的理想选择。Pyppeteer是一个强大的Python库&#xff0c;它可以让你控制浏览器进行自动化操作&#xff0c;如点击按钮、填写表单等&#xff0c;从而实现数据的…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...