缺失的第一个正数

思路:我的初步想法是先对数组排序,然后找到第一个正数的位置,从1开始顺序比对:哪个没出现就是答案。

代码:


class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());int ans=0;int zs_poition=0;for(int i=0;i<nums.size();i++){if(nums[i]>0){zs_poition=i;//第一个正整数的位置,从这里开始比对break;}}for(int i =zs_poition,zzs=1;i<nums.size();i++){if(zzs!=nums[i]){ans=zzs;break;}if(i==nums.size()-1){ans=zzs+1;}zzs++;}return ans;}
};

巨呆逼的方法 还错了。。。。。。。

        分析了一下错误样例,原因就是没有考虑重复数字,可以排序后进行一次去重。也可以在后面专门处理一下有重复数字的情况。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());int ans=0;int zs_poition=0;for(int i=0;i<nums.size();i++){ if(nums[i]>0){zs_poition = i;//第一个正整数的位置,从这里开始比对break;}}for(int i =zs_poition,zzs=1;i<nums.size();i++)  {// 处理重复数字            if(zzs!=nums[i]){if(i==0){ans=zzs;break;}else if(i>0&&nums[i]!=nums[i-1]){ans=zzs;break;}else{zzs--;}}if(i==nums.size()-1){ans=zzs+1;}zzs++;}return ans;}
};

现在是全部过了。但是用了排序,算是作弊了吧,排序是nlogn    题目要求时间复杂度On,且常数级别的空间复杂度。

看看题解:

都太巧妙了。

我们用排序的也太复杂了:

这样不用考虑重复的问题。但是都是不满足O(n)或者另外开了空间的。

但我们也来写一些代码来练一下手吧。

法一:哈希表

注意 哈希表的增加元素是用insert()方法。

这里用一个简单的set就可以了,只要存键。
 

class Solution {
public:int firstMissingPositive(vector<int>& nums) {unordered_set<int> q;for(auto t:nums){q.insert(t);}for(int i=1;;i++){if(!q.count(i)){return i;}}}
};

法二On^2就算了

实在是太妙了下面这个解法,一定要温故而知新:

 主要思路:

        要明白,缺失的正整数一定在[1,N+1]中,其中N 为数组的长度。

这道题的灵感就是从哈希表中得到的,可以对数组进行标记。

        首先,由于缺失的正整数一定在[1,N+1]中:若[1,N]都存在,则缺失的为N+1,否则,缺失的正整数就在[1,N]中。

        首先,对数组中小于1的数进行赋值,就赋值为N+1即可。

        然后遍历一次数组,将遍历到的值在[1,N]中的对应位置加上负号(打上标记),代表这个位置所代表的正整数是在数组中存在的。

        由于会出现负数,(被标记过了),故在进行遍历的时候,取绝对值来判断。

最后,再遍历一遍数组,若所有的位置都被打上了标记(全部为负数),则第一个缺失的正整数即为N+1。

这样子写的代码就是O(n)且没有开其他的空间。

代码:

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n =nums.size();for(int i=0;i<n;i++){if(nums[i]<1){nums[i]=n+1;//处理一下本来的负数和0,以免影响标记}}for(int i=0;i<n;i++)//遍历整个数组{int t=abs(nums[i]);if(t>=1&&t<=n){nums[t-1]=-abs(nums[t-1]);//如果满足要求,将对应位置改为负数,已经是负的不用再处理一次。}}int ans=0;for(int i=0;i<n;i++)//重新遍历{if(nums[i]>0)//有大于零的  则i+1则为缺的那个正整数{ans=i+1;break;}}return ans==0?n+1:ans;//若ans还是等于0,则代表1~N在数组中都有,缺失的正整数为N+1;}
};

        

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

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

相关文章

常见中间件漏洞复现之【Apache】!

CVE-2021-41773 Apache HTTP Server 路径穿越漏洞 漏洞简介 该漏洞是由于Apache HTTP Server 2.4.49版本存在⽬录穿越漏洞,在路径穿越⽬录 <Directory/>Require all granted</Directory>允许被访问的的情况下&#xff08;默认开启&#xff09;&#xff0c;攻击者…

WEB渗透Web突破篇-WAF绕过

SQL注入分块传输 https://github.com/c0ny1/chunked-coding-converter跑注入点被拦截使用分块传输&#xff0c;右键选择使用SQLMAP跑注入>python sqlmap.py -r 1.txt --batch --proxyhttp://127.0.0.1:8080 --dbs自动提供可用的tamper Atlas GitHub - m4ll0k/Atlas: Quick…

常见中间件漏洞复现之【Tomcat】!

Tomcat介绍 tomcat是⼀个开源⽽且免费的jsp服务器&#xff0c;默认端⼝ : 8080&#xff0c;属于轻量级应⽤服务器。它可以实现 JavaWeb程序的装载&#xff0c;是配置JSP&#xff08;Java Server Page&#xff09;和JAVA系统必备的⼀款环境。 在历史上也披露出来了很多的漏洞 …

解决windows安装docker desktop打开报错问题

下载docker windows版本: https://desktop.docker.com/win/main/amd64/Docker%20Desktop%20Installer.exe?utm_sourcedocker&utm_mediumwebreferral&utm_campaigndd-smartbutton&utm_locationmodule 正常安装&#xff0c;然后运行&#xff0c;弹出这个报错: 试了…

组件设计原则

state数据结构设计 用数据描述所有内容数据要结构化&#xff0c;易于程序操作&#xff08;遍历、查找&#xff09;数据要可扩展&#xff0c;以便增加新的功能 组件设计组件通讯 从功能上拆分层次尽量让组件原子化容器组件&#xff08;只管理数据&#xff09;& UI组件&am…

非负数、0和正数 限制最大值且保留两位小数在elementpuls表单中正则验证

一、结构 <el-form-item label="单价:" prop="price"><el-inputv-model.trim="formData.price"placeholder="请输入"@blur="formMethod.fixTwo"><template #append>(元)</template></el-input…

VS项目打包成lib库并使用

一、新建一个静态库项目 一般要把项目设为Release模式 二、添加文件 将所需要打包的头文件、源文件添加到该静态库项目中 三、生成项目 生成成功后即可在Release文件夹出现找到相应的.lib文件 四、使用静态库 将静态库文件复制到项目文件夹中&#xff0c;然后在项目属性设…

C++ 几何算法 - 向量点乘,叉乘及其应用

一&#xff1a;点乘介绍 1. 向量点乘&#xff1a; 2. 向量点乘的性质&#xff1a; 3. 向量点乘公式&#xff1a; 4. 向量的点乘的属性&#xff1a; &#xff08;1&#xff09;&#xff1a;向量与自身做点乘&#xff0c;会得到向量长度的平方&#xff1a; &#xff08;2&#xf…

看门狗应用编程-I.MX6U嵌入式Linux C应用编程学习笔记基于正点原子阿尔法开发板

看门狗应用编程 看门狗应用编程介绍 看门狗定时器的基本概念 看门狗是一个可以在一定时间内被复位/重置的计数器 如果在规定时间内没有复位&#xff0c;看门狗计时器溢出会对CPU产生复位信号使系统重启 有些看门狗可以只产生中断信号而不会使系统复位 I.MX6UL/I.MX6ULL So…

尚品汇-创建ES索引库(二十七)

目录&#xff1a; &#xff08;1&#xff09;商品检索功能介绍 &#xff08;2&#xff09;根据业务搭建数据结构 &#xff08;3&#xff09;nested 介绍 &#xff08;4&#xff09;搭建service-list服务 &#xff08;5&#xff09;构建实体与es mapping建立映射关系 &…

常见中间件漏洞复现之【Jboss】!

Jboss介绍 JBoss是⼀个基于J2EE的开发源代码的应⽤服务器。JBoss代码遵循LGPL许可&#xff0c;可以在任何商业应⽤中免费使⽤。JBoss是⼀个管理EJB的容器和服务器&#xff0c;⽀持EJB1.1、EJB 2.0和EJB3的规范。但JBoss核⼼服务不包括⽀持servlet/JSP的WEB容器&#xff0c;⼀般…

常见中间件漏洞复现之【WebLogic】!

Weblogic介绍 WebLogic是美国Oracle公司出品的⼀个application server&#xff0c;确切的说是⼀个基于JAVAEE架构的中间件&#xff0c;默认端⼝&#xff1a;7001 WebLogic是⽤于开发、集成、部署和管理⼤型分布式Web应⽤、⽹络应⽤和数据库应⽤的Java应⽤服务器。将Java的动态…

从C++看C#托管内存与非托管内存

进程的内存 一个exe文件&#xff0c;在没有运行时&#xff0c;其磁盘存储空间格式为函数代码段全局变量段。加载为内存后&#xff0c;其进程内存模式增加为函数代码段全局变量段函数调用栈堆区。我们重点讨论堆区。 托管堆与非托管堆 C# int a10这种代码申请的内存空间位于函…

找工作准备刷题Day21 动态规划算法 (卡尔41期训练营 8.6)

上周有些事情回了趟老家&#xff0c;祝广大博友身体健康&#xff0c;多运动。前面的贪心算法题目后面慢慢补&#xff0c;近期找到了一个实习&#xff0c;大概持续三个月&#xff0c;现在计划是白天工作&#xff0c;晚上下班以后运动运动刷题。要加强牛客网那种两小时3道题的刷题…

Zero123 论文学习

论文链接&#xff1a;https://arxiv.org/abs/2303.11328 代码链接&#xff1a;https://github.com/cvlab-columbia/zero123 解决了什么问题&#xff1f; 人类通常能够仅凭一个相机视角来想象物体的三维形状和外观。这种能力对于日常任务非常重要&#xff0c;例如物体操纵和在…

Ubuntu distro环境搭建

0 Preface/Foreword 1 环境搭建 1.1 安装make工具 sudo apt install make 1.1.1 查看make版本 1.1.2 查看make使用方法 2 搭建交叉编译工具链 2.1 解压交叉工具链到指定路径 命令解释如下&#xff1a; sudo&#xff0c; 表示使用administrative privilegetar&#xff0c;…

3.达梦数据库基础运维管理

文章目录 前言一、基础数据库管理权限角色管理1.1 DM 系统管理员的类型1.2 角色责则分类 DM 数据库2.1 数据库评估2.2 状态和模式 参考内容 前言 本篇博客为上一篇博客的进阶版&#xff0c;主要针对常规达梦数据库的基本管理上面 一、基础数据库管理 权限角色管理 1.1 DM 系…

母带混音插件-Musik Hack Master Plan 1.59 WiN-MAC,长期更新持续有效

Musik Hack Master Plan 1.59 WiN-MAC 一款专业的音频母带制作流程&#xff0c;只需简单的控制就能制作出适合发布的母带&#xff1a; 水晶般清晰的响度、丰富的模拟饱和度、相位一致的成像、物理磁带模拟&#xff0c;以及修复和监听混音的额外工具。 一。Musik Hack Master P…

ViT算法解读——Transformer在分类任务中的应用

论文&#xff1a;An image is worth 16x16 words: Transformers for image recognition at scale 作者&#xff1a;Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg…

Golang | Leetcode Golang题解之第322题零钱兑换

题目&#xff1a; 题解&#xff1a; func coinChange(coins []int, amount int) int {var (dfs func(x int) int // x金额 最少硬币个数memo make(map[int]int) // 记忆化)dfs func(x int) int {//边界if x 0 {return 0} else if x < 0 {return math.MaxInt32}//记…