LeetCode 41 缺失的第一个正数

news/2024/2/24 7:00:22/文章来源:https://blog.csdn.net/qq_43745578/article/details/135623792

题目描述

缺失的第一个正数

给你一个未排序的整数数组 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

解法

如果本题没有额外的时空复杂度要求,那么就很容易实现:

  • 我们可以将数组所有的数放入哈希表,随后从 111 开始依次枚举正整数,并判断其是否在哈希表中;
  • 我们可以从 111 开始依次枚举正整数,并遍历数组,判断其是否在数组中。

如果数组的长度为 N,那么第一种做法的时间复杂度为 O(N),空间复杂度为 O(N);第二种做法的时间复杂度为 O(N^2),空间复杂度为 O(1)。但它们都不满足时间复杂度为 O(N) 且空间复杂度为 O(1)

但是我们可以利用给定数组中的空间来存储一些状态。也就是说,如果题目给定的数组是不可修改的,那么就不存在满足时空复杂度要求的算法;但如果我们可以修改给定的数组,那么是存在满足要求的算法的。

对于上面中提到的第一种做法:

我们可以将数组所有的数放入哈希表,随后从 111 开始依次枚举正整数,并判断其是否在哈希表中。

仔细想一想,我们为什么要使用哈希表?这是因为哈希表是一个可以支持快速查找的数据结构:给定一个元素,我们可以在 O(1)的时间查找该元素是否在哈希表中。因此,我们可以考虑将给定的数组设计成哈希表的「替代产品」。

**实际上,对于一个长度为 N 的数组,其中没有出现的最小正整数只能在 [1,N+1] 中。**这是因为如果 [1, N] 都出现了,那么答案是 N+1,否则答案是 [1,N] 中没有出现的最小正整数。

这样一来,我们将所有在 [1, N]范围内的数放入哈希表,也可以得到最终的答案。而给定的数组恰好长度为 N,这让我们有了一种将数组设计成哈希表的思路:

我们对数组进行遍历,对于遍历到的数 x,如果它在[1,N] 的范围内,那么就将数组中的第 x−1个位置(注意:数组下标从 0开始)打上「标记」。在遍历结束之后,如果所有的位置都被打上了标记,那么答案是 N+1,否则答案是最小的没有打上标记的位置加 1。

那么如何设计这个「标记」呢?由于数组中的数没有任何限制,因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质:由于我们只在意 [1, N] 中的数,因此我们可以先对数组进行遍历,把不在 [1, N] 范围内的数修改成任意一个大于 N 的数(例如 N+1)。这样一来,数组中的所有数就都是正数了,因此我们就可以将「标记」表示为「负号」。算法的流程如下:

  • 我们将数组中所有小于等于 0 的数修改为 N+1;
  • 我们遍历数组中的每一个数 x,它可能已经被打了标记,因此原本对应的数为 |x|,其中 | | 为绝对值符号。如果 ∣x∣∈[1,N],那么我们给数组中的第 |x| - 1 个位置的数添加一个负号。注意如果它已经有负号,不需要重复添加;
  • 在遍历完成之后,如果数组中的每一个数都是负数,那么答案是 N+1,否则答案是第一个正数的位置加 1。

在这里插入图片描述

java代码:

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;// 将负数变为n + 1for (int i = 0; i < n; i++) {if (nums[i] <= 0) {nums[i] = n + 1;}}// 将元素<=n对应的位置变为负数,表示在该位置的元素在1 ~ n范围内for (int i = 0; i < n; i++) {int num = Math.abs(nums[i]);if (num <=  n) {// 注意由于有相同的元素,有可能原来nums[num - 1]的元素由正数变负数,然后又变为正数,所以使用绝对值的负数nums[num - 1] = - Math.abs(nums[num - 1]);}}// 返回第一个大于0的元素下标 + 1for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1;}}return n + 1;}
}

复杂度

  • 时间复杂度:O(N),其中 N 为数组的长度
  • 空间复杂度:O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925855.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

rabbitmq-java基础详解

一、rabbitmq是什么&#xff1f; 1、MQ定义 MQ&#xff08;Message Queue&#xff09;消息队列 主要解决&#xff1a;异步处理、应用解耦、流量削峰等问题&#xff0c;是分布式系统的重要组件&#xff0c;从而实现高性能&#xff0c;高可用&#xff0c;可伸缩和最终一致性的架…

NLP技术在搜索推荐场景中的应用

NLP技术在搜索推荐中的应用非常广泛&#xff0c;例如在搜索广告的CTR预估模型中&#xff0c;NLP技术可以从语义角度提取一些对CTR预测有效的信息&#xff1b;在搜索场景中&#xff0c;也经常需要使用NLP技术确定展现的物料与搜索query的相关性&#xff0c;过滤掉相关性较差的物…

CASAIM与LG化学越南工厂达成全自动化智能测量技术合作,助力汽车锂电池相关零部件全自动化测量及质量管控

近日&#xff0c;CASAIM与LG化学越南工厂达成全自动化智能测量技术合作&#xff0c;CASAIM将为LG化学越南工厂提供最新一代的CASAIM-IS全自动化测量系统解决方案&#xff0c;助力LG化学越南工厂实现汽车锂电池相关零部件的高精度、高效率测量和检测&#xff0c;进一步提升产品质…

【Vue】后端返回文件流,前端预览文件

let date;request({url: this.$route.query.url,method: get,responseType: blob,}).then(resp > {date respthis.path window.URL.createObjectURL(new Blob([resp], {type: "application/pdf"}))}).catch((e) > {//旧版本浏览器下的blob创建对象window.Blo…

Langchain 与 Elasticsearch:创新数据检索的融合实战

1、简介 在信息爆炸的时代&#xff0c;有效地检索和处理数据变得至关重要。Langchain 和 Elasticsearch 的结合&#xff0c;为我们提供了一个强大的工具&#xff0c;以更智能的方式进行数据检索和分析。 作为一名拥有多年 Elasticsearch 实战经验的技术博主&#xff0c;我将在本…

注意:温度太高电路板表面会氧化导致不上锡

不上锡的情况为什么大多发生在热天&#xff1f; 因为天气太热&#xff0c;室内和室外温差太大&#xff0c;如把PCB板从30多度的室外转移到温度更低的室内就会导致PCB板表面“流汗”现象&#xff0c;PCB板表面有水份就会让其氧化PCB板拆封后&#xff0c;SMT工厂内部环境不好或温…

DC电源模块在新能源领域的应用前景

BOSHIDA DC电源模块在新能源领域的应用前景 DC电源模块在新能源领域有着广阔的应用前景。随着可再生能源技术的发展和普及&#xff0c;如太阳能和风能等的应用逐渐增多&#xff0c;DC电源模块在这些领域的应用越来越重要。 首先&#xff0c;DC电源模块可以用于太阳能发电系统…

记一次 .NET某收银软件 非托管泄露分析

一&#xff1a;背景 1. 讲故事 在我的分析之旅中&#xff0c;遇到过很多程序的故障和杀毒软件扯上了关系&#xff0c;有杀毒软件导致的程序卡死&#xff0c;有杀毒软件导致的程序崩溃&#xff0c;这一篇又出现了一个杀毒软件导致的程序非托管内存泄露&#xff0c;真的是分析多…

mac 上 ssh: connect to host localhost port 22: Connection refused

1。 问题 在搭建hadoop环境的时候 发现ssh localhost 在报错 2. 解决 打开系统设置 -> 共享 -> -> 在左边服务中选择 远程登录 注意红框这些选项慎重选择&#xff01;&#xff01;&#xff01; 修改后&#xff0c;在终端再次 ssh localhost 发现登录成功了 如果…

SpringBoot Redis入门(四)——Redis单机、哨兵、集群模式

单机模式&#xff1a;单台缓存服务器&#xff0c;开发、测试环境下使用&#xff1b;哨兵模式&#xff1a;主-从模式&#xff0c;提高缓存服务器的高可用和安全性。所有缓存的数据在每个节点上都一致。每个节点添加监听器&#xff0c;不断监听节点可用状态&#xff0c;一旦主节点…

Vue3 + Vite + Css3切换主题

1、css3中变量的作用 一个系统或者说一个项目中&#xff0c;往往涉及到很多颜色&#xff0c;但是如果系统看起来样式规整统一的话可能在色值方面偏靠一个色系&#xff0c;字体&#xff0c;颜色&#xff0c;背景颜色&#xff0c;图标颜色等等。 所有可以在css中定义统一的变量&…

智能时代,让AI为你撰写专业应用文

大家好我是在看&#xff0c;记录普通人学习探索AI之路。 何谓应用文&#xff1f;简单来说&#xff0c;应用文是指在日常生活中以及工作中撰写的&#xff0c;旨在传递信息、处理事务的一种文体类型。其范畴广泛&#xff0c;涵盖了诸如请假条、通知书、辞职信、检查报告、欠条、…

6.1810: Operating System Engineering 2023 <Lab7 lock: Parallelism/locking>

一、本节任务 二、要点 2.1 文件系统&#xff08;file system&#xff09; xv6 文件系统软件层次如下&#xff1a; 通过路径树我们可以找到相应的文件&#xff1a; fd&#xff08;文件描述符&#xff09;是进程用来标识其打开的文件的手段&#xff0c;每个进程有自己的文件…

SaaS模式、springboot框架医院云HIS系统源码

HIS系统作为医院信息化的核心业务系统&#xff0c;如今已成为各个医疗机构的必备品了。大到三级二级医院&#xff0c;小到社区卫生服务中心&#xff0c;门诊&#xff08;门诊管理系统也可以理解为门诊的his系统&#xff0c;只是功能简单&#xff0c;模块较少&#xff09;。随着…

010:vue结合el-table实现表格小计总计需求(summary-method)

文章目录 1. 实现效果2. 核心部分3. 完整组件代码4. 注意点 1. 实现效果 2. 核心部分 el-table 添加如下配置&#xff0c;添加 show-summary 属性&#xff0c;配置 summary-method 函数 <el-table.......show-summary:summary-method"getSummaries" >...... …

Gartner发布CPS安全2024年预测:安全形势动荡的四大向量

随着威胁形势、自动化和人工智能采用的步伐以及供应商形势不断快速发展&#xff0c;我们为安全和风险管理领导者提供了四项预测&#xff0c;以规划 2024 年及以后 CPS 安全的未来发展方向。 主要发现 随着人工智能的采用加速增加网络物理系统&#xff08; CPS&#xff09;的“智…

【Internet Protocol】ip介绍,如何组局域网实现远程桌面和文件共享

文章目录 1.何为“上网”1.1 定义1.2 为什么连了WiFi就能上网了&#xff1f; 2.ip2.1 什么是ip2.2 为什么区分广域网和局域网&#xff0c;ip的唯一性2.3 如何查看设备的ip2.4 什么叫"ping"2.5 区分是否两个ip是否在同一局域网2.5.1 最稳妥的方式&#xff1a;ip&m…

mysql group_concat函数使用

CREATE TABLE aa (id int(11) DEFAULT NULL,name varchar(50) DEFAULT NULL ) ENGINEInnoDB DEFAULT CHARSETutf8mb41、基本查询 SELECT * FROM aa;2、以id分组&#xff0c;把name字段的值打印在一行&#xff0c;逗号分隔(默认) select id,group_concat(name) from aa group …

精确掌控并发:漏桶算法在分布式环境下并发流量控制的设计与实现

这是《百图解码支付系统设计与实现》专栏系列文章中的第&#xff08;16&#xff09;篇&#xff0c;也是流量控制系列的第&#xff08;3&#xff09;篇。点击上方关注&#xff0c;深入了解支付系统的方方面面。 本篇重点讲清楚漏桶原理&#xff0c;在支付系统的应用场景&#x…

解决打开 json 文件中文乱码的问题

如下图&#xff0c;pycharm 打开是下面的样子 右下角的编码尝试了好久&#xff0c;依然打不开 用代码打开就成功了 import jsonwith open(./Mydata/garbage_classification.json,encodingutf8,moder) as f:data json.load(f) print(data)控制台结果&#xff1a;