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…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
