LeetCode 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
思路
想要实现题目要求的时空限制,可以利用哈希表。
根据题目分析,我们只需要考虑在 [ 1,numsize ]范围内的数据,如果数据都不在该范围内,则应该返回 1。构建哈希表的哈希方法是:该范围内数的地址 = 数值减一,然后将该地址标记,标记方法为取负,在此之前,需要将所有小于等于0的数换为 numsize+1。
标记之后遍历数组,出现的第一个正数的下标加1便是结果。
代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>int firstMissingPositive(int *nums, int numsSize);int main()
{int size = 2;int nums[4] = {2, 1};int res = firstMissingPositive(nums, size);printf("%d", res);return 0;
}int firstMissingPositive(int *nums, int numsSize)
{for (int i = 0; i < numsSize; i++){if (nums[i] <= 0){nums[i] = numsSize + 1;}}for (int i = 0; i < numsSize; i++){int t = fabs(nums[i]);if (t < numsSize + 1 && nums[t - 1] > 0){nums[t - 1] = -nums[t - 1];}}int i;for (i = 0; i < numsSize; i++){if (nums[i] >= 0){break;}}return i + 1;
}
相关文章:
LeetCode 41题:缺失的第一个正数
目录 题目 思路 代码 题目 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1: 输入:nums [1,2,0] 输出:3示例 2ÿ…...
学单片机有什么用?
单片机简而言之就是一个小计算机系统,它已经应用到了我们生活中的方方面面。单片机比专用处理器适合应用于嵌入式系统,因此它得到了多的应用,事实上单片机是世界上数量多的计算机。 现代人类生活中所用的几乎每件电子和机械产品中都会集成有单…...
Go 1.21新增的 slices 包详解(二)
Go 1.21新增的 slices 包提供了很多和切片相关的函数,可以用于任何类型的切片。 slices.Delete 定义如下: func Delete[S ~[]E, E any](s S, i, j int) S 从 s 中删除元素 s[i:j],返回修改后的切片。如果 s[i:j] 不是 s 的有效切片&#…...
解决charles无法抓取localhost数据包
我们有时候在本地调试的时候,使用charles抓取向本地服务发送的请求的,发现无法抓取。 charles官方也作了相应说明: 大概意思就是 某些系统使用的是硬编码不能使用localhost进行传输,所以当我们连接到 localhost的时候,…...
基于注解优雅的实现接口幂等性
一、什么是幂等性 简单来说,就是对一个接口执行重复的多次请求,与一次请求所产生的结果是相同的,听起来非常容易理解,但要真正的在系统中要始终保持这个目标,是需要很严谨的设计的,在实际的生产环境下&…...
flutter:webview_flutter和flutter_inappwebview的简单使用
前言 最近在研究如何在应用程序中嵌入Web视图,发现有两个库不错。 一个是官方维护、一个是第三方维护。因为没说特别的需求,就使用了官方库,实现一些简单功能是完全ok的 webview_flutter 不建议使用,因为效果不怎么样…...
opencv进阶09-视频处理cv2.VideoCapture示例(打开本机电脑摄像头)
视频信号(以下简称为视频)是非常重要的视觉信息来源,它是视觉处理过程中经常要处理的一类信号。实际上,视频是由一系列图像构成的,这一系列图像被称为帧,帧是以固定的时间间隔从视频中获取的。获取…...
大语言模型与语义搜索;钉钉个人版启动内测,提供多项AI服务
🦉 AI新闻 🚀 钉钉个人版启动内测,提供多项AI服务 摘要:钉钉个人版正式开始内测,面向小团队、个人用户、高校大学生等人群。该版本具有AI为核心的功能,包括文生文AI、文生图AI和角色化对话等。用户可通过…...
小程序-基于vant的Picker组件实现省市区选择
一、原因 因vant/area-data部分的市/区数据跟后台使用的高德/腾讯省市区有所出入,故须保持跟后台用同一份数据,所以考虑以下几个组件 1、Area 2、Cascader 3、Picker 因为使用的是高德地图的省市区json文件,用area的话修改结构代价太大&…...
智慧水利利用4G物联网技术实现远程监测、控制、管理
智慧水利工业路由器是集合数据采集、实时监控、远程管理的4G物联网通讯设备,能够让传统水利系统实现智能化的实时监控和远程管理。工业路由器利用4G无线网络技术,能够实时传输数据和终端信息,为水利系统的运维提供有效的支持。 智慧水利系统是…...
sql server Varchar转换为Datetime
将Varchar转换为Datetime是一个常见的需求,在处理日期和时间数据时特别有用。在SQL Server中,可以使用CONVERT函数或CAST函数将Varchar转换为Datetime。 使用CONVERT函数 CONVERT函数可以将一个值从一个类型转换为另一个类型。以下是使用CONVERT函数将…...
什么文件传输协议才能保障跨国文件传输安全又稳定
在当今的全球化时代,跨国文件传输是一种常见而又重要的需求,无论是个人还是企业,都需要通过网络来分享和交换各种类型和大小的文件。但是,跨国文件传输也面临着许多挑战和风险,如何选择一个合适的文件传输协议…...
LeetCode笔记:Weekly Contest 359
LeetCode笔记:Weekly Contest 359 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接:https://leetcode.com/contest/weekly-contest-359 1. 题目一 …...
使用Java和ChatGPT Api来创建自己的大模型聊天机器人
文章目录 前言ChatGPT Api简析Chatfunction call Embeddings 制作机器人上下文向量数据库 更多场景介绍扩展阅读 前言 什么是大模型? 大型语言模型(LLM)是一种深度学习模型,它使用大量数据进行预训练,并能够通过提示工…...
Maven介绍_下载_安装_使用_原理
文章目录 1 Maven介绍1.1 Maven是介绍1.2 Maven的作用 2 Maven下载与安装2.1 官网下载2.2 文件目录2.3 环境配置 3 Maven基础概念3.1 仓库分类3.2 依赖坐标3.3 坐标组成 4 Maven配置4.1 本地仓库配置4.2 远程仓库的设置4.3 镜像仓库配置4.4 IDEA配置Maven 5 Maven项目创建5.1 M…...
算法通关村十一关 | 位运算的规则
1.数字在计算机中的表示 机器数:一个数在计算机中的二进制表示形式,叫做这个数的机器数。机器数是自带符号的,在计算机用一个数的最高位存放符号,整数为0,负数为1。比如,十进制中的数3,计算机字…...
【Rust】Rust学习 第十五章智能指针
指针 (pointer)是一个包含内存地址的变量的通用概念。这个地址引用,或 “指向”(points at)一些其他数据。Rust 中最常见的指针是第四章介绍的 引用(reference)。引用以 & 符号为标志并借用…...
炒股怎样加杠杆?关于股票杠杠平台比例的选择知识分析
在股票市场中,加杠杆是一种常见的投资策略,可以帮助投资者提升收益,但也伴随着更高的风险。本文将介绍炒股加杠杆的具体步骤和股票杠杆平台比例选择的知识分析,帮助读者更好地了解并使用这一策略。 一、炒股加杠杆的步骤 1. 选择…...
【jenkins】jenkins流水线构建打包jar,生成docker镜像,重启docker服务的过程,在jenkins上一键完成,实现提交代码自动构建的功能
【jenkins】jenkins流水线构建打包jar,生成docker镜像,重启docker服务的过程,在jenkins上一键完成,实现提交代码自动构建,服务重启,服务发布的功能。一键实现。非常的舒服。 1. 启动脚本 shell脚本 这是 s…...
Pytest使用fixture实现token共享
同学们在做pytest接口自动化时,会遇到一个场景就是不同的测试用例需要有一个登录的前置步骤,登录完成后会获取到token,用于之后的代码中。首先我先演示一个常规的做法。 首先在conftest定义一个login的方法,方法返回token pytes…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
C#最佳实践:为何优先使用as或is而非强制转换
C#最佳实践:为何优先使用as或is而非强制转换 在 C# 的编程世界里,类型转换是我们经常会遇到的操作。就像在现实生活中,我们可能需要把不同形状的物品重新整理归类一样,在代码里,我们也常常需要将一个数据类型转换为另…...
Docker环境下安装 Elasticsearch + IK 分词器 + Pinyin插件 + Kibana(适配7.10.1)
做RAG自己打算使用esmilvus自己开发一个,安装时好像网上没有比较新的安装方法,然后找了个旧的方法对应试试: 🚀 本文将手把手教你在 Docker 环境中部署 Elasticsearch 7.10.1 IK分词器 拼音插件 Kibana,适配中文搜索…...
开疆智能Ethernet/IP转Modbus网关连接鸣志步进电机驱动器配置案例
在工业自动化控制系统中,常常会遇到不同品牌和通信协议的设备需要协同工作的情况。本案例中,客户现场采用了 罗克韦尔PLC,但需要控制的变频器仅支持 ModbusRTU 协议。为了实现PLC 对变频器的有效控制与监控,引入了开疆智能Etherne…...
【系统架构设计师-2025上半年真题】综合知识-参考答案及部分详解(回忆版)
更多内容请见: 备考系统架构设计师-专栏介绍和目录 文章目录 【第1题】【第2题】【第3题】【第4题】【第5题】【第6题】【第7题】【第8题】【第9题】【第10题】【第11题】【第12题】【第13题】【第14题】【第15题】【第16题】【第17题】【第18题】【第19题】【第20~21题】【第…...
鸿蒙APP测试实战:从HDC命令到专项测试
普通APP的测试与鸿蒙APP的测试有一些共同的特征,但是也有一些区别,其中共同特征是,它们都可以通过cmd的命令提示符工具来进行app的性能测试。 其中区别主要是,对于稳定性测试的命令的区别,性能指标获取方式的命令的区…...
