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

LeetCode 题解 41. 缺失的第一个正数

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
解释:范围 [1,2] 中的数字都在数组中。
示例 2:
输入:nums = [3,4,-1,1]
输出:2
解释:1 在数组中,但 2 没有。
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
解释:最小的正数 1 没有出现。
提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1

题解

题目看起来很简单,寻找未出现过的最小正整数

很自然的想法就是用哈希表统计各个数字出现的次数,然后从1开始递增寻找是否出现过,第一个未出现的数字就是答案

但是注意到题目的要求是只使用常数级别额外空间的解决方案,也就是说不能开辟一个哈希表,需要在原数组上进行操作

接着对题目进行分析,我们发现:对于 n 个数的数组,最大的答案为 n+1,即数组内是 1,2,3…n 这些数各一个
否则只要有任何一个 1~n 之外或者重复的数,那么1~n之间必定有数字没出现,最小的即为我们的答案

  • 所以答案在 1~n+1 之间,而对于数组我们只关心 1~n 之间的数字,其余的数字对答案没有影响

接下来我们考虑如何在数组内原地操作

由于我们仅关心 1~n 的数字,而原数组恰好又是 n 大小,不妨将原数组作为哈希表,记录 1~n
用 nums[i] 记录 i+1
我们并不能直接用 nums[i] 记录 i+1 出现的次数,因为原数组内存储着需要的数据,不能直接修改原数组中的数据
那么我们不妨“一个萝卜一个坑",将 nums[i] 放到下标为 nums[i]-1 的位置上,并且考虑到不能修改原数组,我们将 nums[i] 与 nums[nums[i]-1] 进行交换,于是我们遍历数组,将数字放到对应的位置上,最后再遍历数组,第一个数字与位置不对的位置就是我们的答案

实现细节

  1. 遍历数组,此时位置为 i
  2. 如果 nums[i] 在 1~n 之外,我们不用处理它,因为它对答案没有影响
  3. 如果 nums[i] 在 1~n 之间,我们需要判断位置 nums[i]-1 上是否已经放置了对应的数 num[i]它是否在位置 nums[i]-1 上) ,没有的话就将其与对应位置的数进行交换,否则同样不做处理
  4. 然后我们接着看位置 i 上换来的新数据,重复以上过程
  5. 位置 i 处理结束后 i++
  • 注意,数组中会含有重复的数据
    因此步骤3我们不能去直接判断数字 nums[i] 是否在对应位置 nums[i]-1 上
    因为位置 nums[i]-1 上的数可能是另一个 nums[i],这样我们交换后再看换来的 nums[i],由于 nums[i] 不在对应位置,会接着把之前换过去的 nums[i] 换回来,这样就死循环了
    为了应对这种情况,我们直接去判断 nums[i] 对应的位置上是否是正确的数,是正确的数就不用处理了,多余的数和范围外的数一样对答案没有影响,这样面对重复的数字就不会一直交换了

代码如下↓

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n=nums.size();int res=n+1;for(int i=0;i<n;i++){if(nums[i]>=1 && nums[i]<=n && nums[i]!=nums[nums[i]-1]){swap(nums[nums[i]-1],nums[i]);i--;}}for(int i=0;i<n;i++){if(nums[i]!=i+1){res=i+1;break;}}return res;}
};

相关文章:

LeetCode 题解 41. 缺失的第一个正数

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

3337. 字符串转换后的长度 II

3337. 字符串转换后的长度 II # 定义了一个大质数 MOD&#xff0c;用于取模运算&#xff0c;防止数值溢出。 MOD 1_000_000_007# 矩阵乘法 mul def mul(a:List[List[int]], b:List[List[int]]) -> List[List[int]]:# 输入两个矩阵 a 和 b&#xff0c;返回它们的矩阵乘积 a…...

基于 TensorFlow 框架的联邦学习可穿戴设备健康数据个性化健康管理平台研究

基于 TensorFlow 框架的联邦学习可穿戴设备健康数据个性化健康管理平台研究 摘要: 随着可穿戴设备的普及,人们对于自身健康管理的需求日益增长。然而,可穿戴设备所收集的健康数据往往分散在不同用户的设备中,且涉及用户隐私敏感信息。本研究旨在构建一个基于 TensorFlow 框…...

查看字节真实二进制形式示例解析1

查看字节的真实二进制形式&#xff1f; 若需要显式查看二进制0/1&#xff0c;可以通过以下方法转换&#xff1a; 方法1&#xff1a;逐字节转换为二进制字符串 def bytes_to_binary(data: bytes) -> str:return .join([bin(byte)[2:].zfill(8) for byte in data])# 示例 …...

hadoop中spark基本介绍

Spark是一个基于内存计算的快速、通用、可扩展的大数据处理引擎&#xff0c;可与Hadoop集成并在其生态系统中发挥重要作用。以下是其基本介绍&#xff1a; 特点 - 快速&#xff1a;基于内存计算&#xff0c;能将中间结果缓存在内存中&#xff0c;避免频繁读写磁盘&#xff0c;大…...

Apollo学习——键盘控制速度

# keyboard_control.py import time import keyboard # 键盘输入模块 pip install keyboard from getkey import getkey, keys from cyber.python.cyber_py3 import cyber_time from cyber.python.cyber_py3 import cyber from modules.common_msgs.control_msgs import contro…...

无人机数据处理与特征提取技术分析!

一、运行逻辑 1. 数据采集与预处理 多传感器融合&#xff1a;集成摄像头、LiDAR、IMU、GPS等传感器&#xff0c;通过硬件时间戳或PPS信号实现数据同步&#xff0c;确保时空一致性。 边缘预处理&#xff1a;在无人机端进行数据压缩&#xff08;如JPEG、H.265&#xff09;…...

Java内存马的检测与发现

【网络安全】Java内存马的检测与发现 一、Java内存马的现象二、检测思路三、重点关注类四、检测方法1. 检查方法&#xff08;FindShell&#xff09;2. 检查方法&#xff08;sa-jdi&#xff09;3. 检查方法&#xff08;arthas-boot&#xff09;4. 检查方法&#xff08;cop.jar&a…...

基于策略的强化学习方法之策略梯度(Policy Gradient)详解

在前文中&#xff0c;我们已经深入探讨了Q-Learning、SARSA、DQN这三种基于值函数的强化学习方法。这些方法通过学习状态值函数或动作值函数来做出决策&#xff0c;从而实现智能体与环境的交互。 策略梯度是一种强化学习算法&#xff0c;它直接对策略进行建模和优化&#xff0c…...

未来软件开发趋势与挑战

未来软件开发的方向将受到技术进步、市场需求和社会变革的多重影响。以下是可能主导行业发展的关键趋势&#xff1a; 1. AI与自动化深度整合 AI代码生成&#xff1a;GitHub Copilot等工具将进化成"AI开发伙伴"&#xff0c;能理解业务逻辑并自动生成完整模块。自修复…...

【vue】生命周期钩子使用

一、详解 created&#xff1a;实例化完成还没有渲染 mounted&#xff1a;渲染完成 二、应用 在created之后获取网络请求&#xff0c;封装成函数&#xff0c;在需要的地方直接调用函数...

【CTFShow】Web入门-信息搜集

Web1 好长时间没刷题了&#xff0c;第一眼看到的时候有点儿手足无措 在信息搜集中最常用的手段就是直接查看源代码&#xff0c;所以直接F12大法吧&#xff0c;果不其然拿到了flag Web2 题目给了提示js前台拦截 无效操作 打开题看到界面还是一脸茫然 坏了&#xff0c;这波貌似…...

Go 语言 net/http 包使用:HTTP 服务器、客户端与中间件

Go 语言标准库中的net/http包十分的优秀&#xff0c;提供了非常完善的 HTTP 客户端与服务端的实现&#xff0c;仅通过几行代码就可以搭建一个非常简单的 HTTP 服务器。几乎所有的 go 语言中的 web 框架&#xff0c;都是对已有的 http 包做的封装与修改&#xff0c;因此&#xf…...

YOLO v2:目标检测领域的全面性进化

引言 在YOLO v1取得巨大成功之后&#xff0c;Joseph Redmon等人在2016年提出了YOLO v2&#xff08;也称为YOLO9000&#xff09;&#xff0c;这是一个在准确率和速度上都取得显著提升的版本。YOLO v2不仅保持了v1的高速特性&#xff0c;还通过一系列创新技术大幅提高了检测精度…...

卓力达红外热成像靶标:革新军事训练与航空检测的关键技术

引言 红外热成像技术凭借其非接触、无辐射、全天候工作的特性&#xff0c;已成为现代军事和航空领域的重要工具。南通卓力达研发的**自发热红外热成像靶标**&#xff0c;通过创新设计与制造工艺&#xff0c;解决了传统训练器材的痛点&#xff0c;并在军事和航空应用中展现出显…...

【生产实践】Dolphinscheduler集群部署后Web控制台不能登录问题解决

太长不看版 问题描述&#xff1a; Dolphinscheduler按生产手册使用一键脚本集群部署后&#xff0c;控制台登录页面可以打开&#xff0c;但使用默认账户怎么都登录不进去&#xff0c;尝试在数据库中清理登录用户字段&#xff0c;发现数据库中并没有相关用户字段&#xff0c;而后…...

Shell和Bash介绍

Shell是硬件和软件之间的交互界面。Bash是一种shell&#xff0c;在Linux系统中比较常见。我目前使用的Mac用的Z shell(zsh). 可以在terminal里面通过zsh命令对系统进行操作。这是与Windows所见所得&#xff0c;用鼠标点相比&#xff0c;Mac和Linux都可以完全用命令操作。常用的…...

数据 分析

应用统计和计算方法,识别数据特征与规律. 1 分析方法 1.1 描述性分析 总结和呈现数据的基本特征;特点是简单直观. 1.1.1 集中趋势分析 ①均值:数据总和除以数据个数,反映数据的平均水平;特点是易受极端值影响;用于了解整体平均情况,例如计算班级学生平均成绩. ②中位数:将数…...

纯css实现蜂窝效果

<!DOCTYPE html><html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>蜂窝效果</title><style>body {margin: 0…...

用PyTorch在超大规模下训练深度学习模型:并行策略全解析

我猜咱们每个人肯定都累坏了&#xff0c;天天追着 LLM 研究社区跑&#xff0c;感觉每天都冒出个新的最牛模型&#xff0c;把之前的基准都给打破了呢。要是你好奇为啥创新速度能这么快&#xff0c;那主要就是研究人员能够在超大规模下训练和验证模型啦&#xff0c;这全靠并行计算…...

linux-进程信号捕捉

1. 信号捕捉流程 操作系统会在合适的时候处理信号&#xff0c;那这个合适的时候是什么时候呢&#xff1f;进程从内核态返回到用户态的时候。 假如用户程序注册了 SIGQUIT 信号的处理函数 sighandler。当程序正在执行 main 函数时&#xff0c;如果发生中断、异常或系统调用&…...

【免杀】C2免杀技术(三)shellcode加密

前言 shellcode加密是shellcode混淆的一种手段。shellcode混淆手段有多种&#xff1a;加密&#xff08;编码&#xff09;、偏移量混淆、UUID混淆、IPv4混淆、MAC混淆等。 随着杀毒软件的不断进化&#xff0c;其检测方式早已超越传统的静态特征分析。现代杀软往往会在受控的虚…...

人工智能驱动的临床路径体系化解决方案与实施路径

引言 临床路径管理作为现代医疗质量管理的重要工具,其核心在于通过标准化诊疗流程来提升医疗服务的规范性、一致性和效率。然而,传统临床路径管理面临路径设计僵化、执行依从性低、变异管理滞后等诸多挑战,亟需借助人工智能技术实现转型升级。本研究旨在探讨如何通过构建系…...

旋变信号数据转换卡 旋变解码模块 汽车永磁同步电机维修工具

旋变信号数据转换卡&#xff0c;是一款专门针对与永磁同步电机的旋变编码器和 BRX 型旋转变压器编码器进行旋变信号解码转换串行总线协议的专用转换卡。此款转换卡结合了专用的旋变信号解码芯片解码逻辑处理&#xff0c;解码信号分辨率高、线性度高、响应速度快。板卡采用工业级…...

RPM 包制作备查 SRPM 包编译

&#x1f308; 个人主页&#xff1a;Zfox_ 目录 &#x1f525; 前言 一&#xff1a;&#x1f525; 准备 二&#xff1a;&#x1f525; 制作 rpm 1.设置目录结构&#xff08;制作车间&#xff09;2. 源码放置到规划好的目录当中3. 创建一个spec文件&#xff0c;指挥如何使用这些…...

[学习] RTKLib详解:rtcm2.c、rtcm3.c、rtcm3e与rtcmn.c

RTKLib详解&#xff1a;rtcm2.c、rtcm3.c、rtcm3e与rtcmn.c 本文是 RTKLlib详解 系列文章的一篇&#xff0c;目前该系列文章还在持续总结写作中&#xff0c;以发表的如下&#xff0c;有兴趣的可以翻阅。 [学习] RTKlib详解&#xff1a;功能、工具与源码结构解析 [学习]RTKLib详…...

MCU ESP32-S3+SD NAND(贴片式T卡):智能皮电手环(GSR智能手环)性能与存储的深度评测

在智能皮电手环与数据存储领域&#xff0c;主控MCU ESP32-S3FH4R2 与 存储SD NAND MKDV2GIL-AST 的搭档堪称行业新典范。二者深度融合低功耗、高速读写、SMART 卓越稳定性等核心优势&#xff0c;以高容量、低成本的突出特性&#xff0c;为大规模生产场景带来理想的数据存储方案…...

股指期货套期保值怎么操作?

股指期货套期保值就是企业或投资者通过持有与其现货市场头寸相反的期货合约&#xff0c;来对冲价格风险的一种方式。换句话说&#xff0c;就是你在股票市场上买了股票&#xff08;现货&#xff09;&#xff0c;担心股价下跌会亏钱&#xff0c;于是就在期货市场上卖出相应的股指…...

Pytorch的Dataloader使用详解

PyTorch 的 DataLoader 是数据加载的核心组件&#xff0c;它能高效地批量加载数据并进行预处理。 Pytorch DataLoader基础概念 DataLoader基础概念 DataLoader是PyTorch基础概念 DataLoader是PyTorch中用于加载数据的工具&#xff0c;它可以&#xff1a;批量加载数据&#xf…...

Ros2 - Moveit2 - DeepGrasp(深度抓握)

本教程演示了如何在 MoveIt 任务构造器中使用抓握姿势检测 (GPD)和 Dex-Net 。 GPD&#xff08;左&#xff09;和 Dex-Net&#xff08;右&#xff09;用于生成拾取圆柱体的抓取姿势。 https://moveit.picknik.ai/main/_images/mtc_gpd_panda.gif 入门 如果您还没有这样做&am…...

【DRAM存储器五十一】LPDDR5介绍--CK、WCK、RDQS单端模式、Thermal Offset、Temperature Sensor

👉个人主页:highman110 👉作者简介:一名硬件工程师,持续学习,不断记录,保持思考,输出干货内容 参考资料:《某LPDDR5数据手册》 、《JESD209-5C》 目录 CK、WCK、RDQS单端模式 Thermal Offset Temperature Sensor...

【springcloud学习(dalston.sr1)】Eureka 客户端服务注册(含源代码)(四)

d该系列项目整体介绍及源代码请参照前面写的一篇文章【springcloud学习(dalston.sr1)】项目整体介绍&#xff08;含源代码&#xff09;&#xff08;一&#xff09; 这篇文章主要介绍Eureka客户端服务注册到eureka的server端。 上篇文章【springcloud学习(dalston.sr1)】Eurek…...

数据结构 栈和队列

文章目录 &#x1f4d5;1.栈(Stack)✏️1.1 栈的基本操作✏️1.2 栈的模拟实现&#x1f516;1.2.1 构造方法&#x1f516;1.2.2 扩容方法&#x1f516;1.2.3 判断栈是否为空或是否满&#x1f516;1.2.4 存储元素&#x1f516;1.2.5 删除元素&#x1f516;1.2. 6 获取栈顶元素 ✏…...

[数据结构]5. 栈-Stack

栈-Stack 1. 介绍2. 栈的实现2.1 基于链表的实现2.2 基于数组的实现 3. 栈操作CreateInitilizateDestoryPushPopTopEmptySize 1. 介绍 栈&#xff08;stack&#xff09; 是一种遵循先入后出逻辑的线性数据结构。顶部称为“栈顶”&#xff0c;底部称为“栈底”。把元素添加到栈…...

Git的安装和配置(idea中配置Git)

一、Git的下载和安装 前提条件&#xff1a;IntelliJ IDEA 版本是2023.3 &#xff0c;那么配置 Git 时推荐使用 Git 2.40.x 或更高版本 下载地址&#xff1a;CNPM Binaries Mirror 操作&#xff1a;打开链接 → 滚动到页面底部 → 选择2.40.x或更高版本的 .exe 文件&#xf…...

QT-1.信号与槽

一、信号与槽机制概述 四、信号与槽的连接 六、自定义信号与槽 思考 定义与作用 &#xff1a;信号与槽是Qt中的核心通信机制&#xff0c;用于实现对象间的数据交互和事件处理。当特定事件发生时&#xff0c;对象会发出信号&#xff0c;而与之相连的槽函数会被自动调用。 特点 …...

常用的应用层网络协议对比

概述 协议通信模式加密支持传输层主要特点典型应用场景WSS全双工是&#xff08;TLS/SSL&#xff09;TCP安全的实时双向通信实时聊天、在线游戏WebSocket (WS)全双工否TCP持久连接、低延迟协同编辑、实时通知HTTPS请求-响应是&#xff08;TLS/SSL&#xff09;TCP安全性强、兼容…...

数据结构与算法:状压dp

前言 状压dp在整个动态规划专题里特别重要,用位信息表示元素的思想更是重中之重。 一、状态压缩 1.内容 对于一些带路径的递归,通常来讲没法改记忆化搜索和严格位置依赖的动态规划。但如果这个路径的数据量在一定范围内,就可以考虑使用一个整数status的位信息0和1来存路…...

Spring Cloud Gateway 聚合 Swagger 文档:一站式API管理解决方案

前言 在微服务架构中&#xff0c;随着服务数量的增加&#xff0c;API文档管理变得越来越复杂。每个微服务都有自己的Swagger文档&#xff0c;开发人员需要记住每个服务的文档地址&#xff0c;这无疑增加了开发难度。本文将介绍如何使用Spring Cloud Gateway聚合所有微服务的Sw…...

Android 适配之——targetSdkVersion 30升级到31-34需要注意些什么?

在Android 16即将到来的之际。也就是targetSdkVersion即将出现36&#xff0c;而30已然会成为历史。那么我的项目已经停留在30很久了。是时候要适配一下适用市场的主流机型了。正常来查找资料的&#xff0c;无非就是已经升级和准备升级targetSdkVersion开发版本。所以你是哪一种…...

网络运维过程中的常用命令

一、通用网络命令 ping 作用&#xff1a;测试与目标 IP 或域名的连通性。 示例&#xff1a; ping www.baidu.com # 持续发送ICMP包 ping -c 4 8.8.8.8 # 发送4个包后停止 traceroute/tracert 功能&#xff1a;追踪数据包经过的路由节点。 示例&#xff1a; traceroute…...

[Java实战]Spring Boot 3整合JWT实现无状态身份认证(二十四)

[Java实战]Spring Boot 3整合JWT实现无状态身份认证&#xff08;二十四&#xff09; 一、JWT简介与核心概念 1. JWT是什么&#xff1f; JSON Web Token (JWT) 是一种开放标准&#xff08;RFC 7519&#xff09;&#xff0c;用于在各方之间安全地传输信息。JWT由三部分组成&am…...

【Java-EE进阶】SpringBoot针对某个IP限流问题

目录 简介 1. 使用Guava的RateLimiter实现限流 添加Guava依赖 实现RateLimiter限流逻辑 限流管理类 控制器中应用限流逻辑 2. 使用计数器实现限流 限流管理类 控制器中应用限流逻辑 简介 针对某个IP进行限流以防止恶意点击是一种常见的反爬虫和防止DoS的措施。限流策…...

软考冲刺——案例分析题 MUX VLAN

上一篇文章介绍了VLAN高级应用的Super VLAN&#xff0c;本次介绍MUX VLAN内容&#xff0c;MUX VLAN在2024.11月考察过选择题&#xff0c;案例题中有可能出现。 考点一&#xff1a;MUX VLAN原理及实现方式&#xff1b;通过简答题出现。 考点二&#xff1a;配置命令填空。 一&…...

Git 用户名与邮箱配置全解析:精准配置——基于场景的参数选择

目录 一、配置查看&#xff1a;理解多层级配置体系二、精准配置&#xff1a;基于场景的参数选择1. 仓库级配置&#xff08;推荐&#xff09;2. 用户级配置3. 系统级配置 三、历史提交信息修改1. 修改最近一次提交2. 修改多个历史提交&#xff08;危险操作&#xff09; 五、配置…...

OpenHarmony平台驱动开发(十七),UART

OpenHarmony平台驱动开发&#xff08;十七&#xff09; UART 概述 功能简介 UART指异步收发传输器&#xff08;Universal Asynchronous Receiver/Transmitter&#xff09;&#xff0c;是通用串行数据总线&#xff0c;用于异步通信。该总线双向通信&#xff0c;可以实现全双工…...

仿生眼机器人(人脸跟踪版)系列之一

文章不介绍具体参数&#xff0c;有需求可去网上搜索。 特别声明&#xff1a;不论年龄&#xff0c;不看学历。既然你对这个领域的东西感兴趣&#xff0c;就应该不断培养自己提出问题、思考问题、探索答案的能力。 提出问题&#xff1a;提出问题时&#xff0c;应说明是哪款产品&a…...

Redis的Pipeline和Lua脚本适用场景是什么?使用时需要注意什么?

Redis Pipeline 和 Lua 脚本详解 一、Pipeline&#xff08;管道&#xff09; 定义 一种批量执行命令的机制&#xff0c;客户端将多个命令一次性发送给服务器&#xff0c;减少网络往返时间&#xff08;RTT&#xff09; 适用场景 ✅ 批量数据操作&#xff08;如万级 key 的写入…...

【Pycharm】pycharm修改注释文字的颜色

一、默认颜色-灰色 这个默认的灰色视觉效果太弱&#xff0c;不便于学习时使用 二、修改颜色 打开Settings 也可以从右上角设置那里打开 还可以快捷键Ctrl&#xff0b;Alt&#xff0b;S打开 找到这个页面把这个√取消掉 然后就能自定义颜色啦...

webgl2着色语言

一、数据类型 标量&#xff1a;布尔型、整型、浮点型 向量&#xff1a;基本类型&#xff1a;bool、int、float 数量 &#xff1a; 2&#xff0c;3&#xff0c;4 矩阵&#xff1a; 移位、旋转、缩放等变换 采样器&#xff1a; 执行纹理采样的相关操作 结构体&#xff1a; 为开…...