《LeetCode热题100》---<5.③普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的五道题

第五道:缺失的第一个正数(困难)

第五道:缺失的第一个正数(困难)

方法一:将数组视为哈希表 

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {if (nums[i] <= 0) {nums[i] = n + 1;}}for (int i = 0; i < n; ++i) {int num = Math.abs(nums[i]);if (num <= n) {nums[num - 1] = -Math.abs(nums[num - 1]);}}for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1;}}return n + 1;}
}

1.将负数,0,替换为n+1变成无效数字,因为我们只关心[1,n]的正数。

2.标记已存在的正整数,对于每一个元素 `nums[i]`,我们用它的绝对值 `num` 来表示。如果num是一个有效的数字,也就是num<=n。那么将数组中索引num-1的元素下标记为负数。这一步结束后,数组中所有出现过的正整数对应的索引位置都会被标记为负数。

3.查找第一个未被标记的位置。查找第一个仍然为正数的元素。此时返回i+1。

4.如果没有找到返回n+1

复杂度分析

  • 时间复杂度:O(N),其中 N 是数组的长度。

  • 空间复杂度:O(1)。

 

方法二:置换(恢复)

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {int temp = nums[nums[i] - 1];nums[nums[i] - 1] = nums[i];nums[i] = temp;}}for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) {return i + 1;}}return n + 1;}
}

除了打标记以外,我们还可以使用置换的方法,将给定的数组「恢复」成下面的形式: 

  • 遍历数组:对于每个元素,将其放置在正确的位置上,即把数字 nums[i] 放在索引 nums[i] - 1 的位置上。通过不断交换,确保每个正整数 k 出现在索引 k-1 的位置上。
  • 检查数组:再遍历一次数组,找到第一个位置 i 使得 nums[i] != i + 1,即第一个缺失的正整数是 i + 1
  • 返回结果:如果所有位置都满足 nums[i] == i + 1,则返回 n + 1,即数组长度加一的值。

复杂度分析

  • 时间复杂度:O(N),其中 N 是数组的长度。

  • 空间复杂度:O(1)。

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

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

相关文章

Python——记录pip问题(解决下载慢、升级失败问题)

在python开发中&#xff0c;经常需要使用到各种各样的库。 pip又是我们常用的安装工具。但是国外的源下载速度实在太慢&#xff0c;经常导致超时。 有很多朋友刚刚学Python的时候&#xff0c;会来问为什么pip下载东西这么慢啊&#xff1f; 而且pycharm里面下载库也是非常的慢…

充电宝有必要买贵的吗?充电宝可以带上高铁吗?充电宝选购方法

市面上的充电宝可以说是非常的多&#xff0c;但是能选到一款适合自己的充电宝基本是不容易的&#xff0c;然而&#xff0c;当我们准备选购充电宝时&#xff0c;常常会面临诸多疑问。其中&#xff0c;“充电宝有必要买贵的吗”就是一个备受关注的问题。价格似乎成为了我们在众多…

pytorch学习笔记4 tensor变换

View/reshape viewreshape, 新版本 要保证数据总量不变&#xff0c;否则报错Squeeze/unsqueeze 减少维度和增加维度 unsqueeze(n): 如果n是正&#xff0c;在第n位前面插1维&#xff08;size1&#xff09;&#xff0c; 如果n是负&#xff0c;在倒数第|n|位后面插入1维&#xf…

将 HuggingFace 模型转换为 GGUF 及使用 ollama 运行 —— 以 Qwen2-0.5B 为例

前言 最近&#xff0c;阿里发布了Qwen2的系列模型&#xff0c;包括0.5B, 1.5B, 7B, 57B-A14B 和 72B&#xff0c;中英文效果都很好。 因为模型太新&#xff0c;目前还没有 GGUF 版本可以下载&#xff0c;于是转下GGUF&#xff0c;并分享转换教程。 什么是 GGUF&#xff1f; …

Linux进程间通信学习2

文章目录 共享内存信号信号概述以及种类信号的处理信号相关函数&#xff08;简单&#xff09;运用小demo实现ctrlc无法终止进程使用kill函数在程序内部实现一个进程杀死另外一个进程 信号相关函数高级版运用函数小demo 信号量信号量相关函数运用小demo: 共享内存 相比于前三个…

快速排序(下)

快速排序&#xff08;下&#xff09; 前言 在上一篇文章中我们了解了快速排序算法&#xff0c;但那是Hoare的版本&#xff0c;其实还有别的版本&#xff1a;一种是挖坑法&#xff0c;它们的区别主要在于如何找基准值。霍尔的版本思路难理解但代码好理解&#xff0c;挖坑法则是…

【Qt开发】调试log日志QDebug重定向输出到textEdit等控件(qInstallMessageHandler回调函数)

【Qt开发】调试log日志QDebug重定向输出到textEdit等控件&#xff08;qInstallMessageHandler回调函数&#xff09; 文章目录 Log输出方式qInstallMessageHandler回调函数线程安全textEdit控件附录&#xff1a;C语言到C的入门知识点&#xff08;主要适用于C语言精通到Qt的C开发…

MySQL:数据类型表的基础操作

目录 1、数据类型 1.1 数值类型 1.2 字符串类型 1.3 日期类型 2、表的基础操作 2.1 选择数据库 2.2 建表 2.3 查看库中所有表 2.4 查看某一表结构 2.5 删表 3、可视化编辑工具 3.1 运行 1、数据类型 1.1 数值类型 bit类型可指定长度&#xff08;如果不写&#xff0c;…

实验八: 彩色图像处理

目录 一、实验目的 二、实验原理 1. 常见彩色图像格式 2. 伪彩色图像 3. 彩色图像滤波 三、实验内容 四、源程序和结果 (1) 主程序(matlab (2) 函数FalseRgbTransf (3) 函数hsi2rgb (4) 函数rgb2hsi (5) 函数GrayscaleFilter (6) 函数RgbFilter 五、结果分析 1. …

清华和字节联合推出的视频理解大模型video-SALMONN(ICML 2024)

video-SALMONN: Speech-Enhanced Audio-Visual Large Language Models 论文信息 paper&#xff1a;https://arxiv.org/abs/2406.15704 code&#xff1a;https://github.com/bytedance/SALMONN/ AI也会「刷抖音」&#xff01;清华领衔发布短视频全模态理解新模型 | ICML 2024 …

基于单片机的防火防盗报警系统设计

摘要&#xff1a; 该多功能防火防盗系统既具有根据环境温度和烟雾浓度进行火灾检测的功能&#xff0c;也有能对人体检测实现防盗的功能。多功能智能防火防盗控制系统的主控制器是 STC89C52 单片机&#xff0c;环境温度的检测采用 DS18B20 &#xff0c; MQ2 检测烟雾浓度&…

[Meachines] [Easy] Mirai Raspberry树莓派默认用户登录+USB挂载文件读取

信息收集 IP AddressOpening Ports10.10.10.48TCP:22,53,80,1276,32400,32469 $ nmap -p- 10.10.10.48 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION 22/tcp open ssh OpenSSH 6.7p1 Debian 5deb8u3 (protocol 2.0) | ssh-hostkey: | 1024 aa:ef:5c:…

@change事件传参

change事件传参 change"(value)>handleChange(value, item,index)" 这样可以接收index参数区分是哪一个组件事件&#xff0c;又可以接收子组件传的value值 <div class"boxItem" v-for"(item, index) in checkPeopleList" :key"inde…

【avue+vue2+elementui】删除、rules、页面跳转、列表数据过长、日期dayjs

这里写目录标题 一、删除二、rules三、页面跳转四、列表数据过长截断五、日期 dayjs一、删除 🍃API/*** 删除.* @param {*} data * @returns 返参*/ export const deleteOrder = (data) => {return request({url: /api/Order/deleteOrder,method: post,data}) }HTML🍃左…

5.2-软件工程基础知识-软件过程模型

软件过程模型 瀑布模型瀑布模型变种-V模型演化模型-原型模型增量模型演化模型-螺旋模型喷泉模型基于构件的开发模型形式化方法模型统一过程模型敏捷方法极限编程其他方法 软件过程模型概述练习题 瀑布模型 瀑布模型(SDLC):瀑布模型是一个经典的生命周期模型&#xff0c;一般将软…

声音和数据之间的调制解调 —— 电报机和电传打字机如何影响计算机的演变

注&#xff1a;机翻&#xff0c;未校对。 The Squeal of Data The through line between the telegraph and the computer is more direct than you might realize. Its influence can be seen in common technologies, like the modem. 电报和计算机之间的直通线比你想象的要…

Redis RDB AOF持久化 主从集群同步原理

RDB RDB Redis数据备份文件 也被叫做Redis数据快照 简单来说就是 把内存中的所有数据记录到磁盘中 当Redis实例故障实例重启后从磁盘读取快照文件恢复数据 快照文件称为RDB文件 默认时保存在当前运行目录执行时机 执行save命令 127.0.0.1:6379> save OK 127.0.0.1:6379&g…

opencascade AIS_TrihedronOwner源码学习对象的实体所有者用于选择管理

opencascade AIS_TrihedronOwner 前言 AIS_Trihedron对象的实体所有者用于选择管理。 在OpenCascade的AIS&#xff08;交互对象框架&#xff09;中&#xff0c;管理类似AIS_Trihedron的对象的选择涉及理解如何处理实体&#xff08;或所有者&#xff09;以进行选择。 方法 1…

正则表达式 空格匹配

目录 一. 前提二. 半角空格 匹配半角空格三. ^ 匹配半角空格开头的半角空格四. ^ $ 匹配整行都是半角空格五. ^[ \t]$ 匹配整行都是半角或Tab空格六. \s 匹配所有空格七. [^\s]匹配除了空格之外的所有内容 一. 前提 &#x1f447;&#x1f447;&#x1f447;有如下所示的内容…

程序员面试 “八股文”在实际工作中是助力、阻力还是空谈?

“八股文”在实际工作中是助力、阻力还是空谈&#xff1f; 作为现在各类大中小企业面试程序员时的必问内容&#xff0c;“八股文”似乎是很重要的存在。但“八股文”是否能在实际工作中发挥它“敲门砖”应有的作用呢&#xff1f;有IT人士不禁发出疑问&#xff1a;程序员面试考…