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…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
