牛客热题:缺失的第一个正整数

牛客热题:数组中出现一次的两个数字> 📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

在这里插入图片描述

文章目录

  • 牛客热题:缺失的第一个正整数
    • 题目链接
    • 方法一:排序
      • 思路
      • 代码
      • 复杂度
    • 方法二:哈希表
      • 思路
      • 代码
      • 复杂度
    • 方法三:原地哈希
      • 思路
      • 代码
      • 复杂度
      • 总结

牛客热题:缺失的第一个正整数

题目链接

缺失的第一个正整数_牛客题霸_牛客网 (nowcoder.com)

方法一:排序

思路

  • step1: 先将数组进行排序
  • step2:引入一个计数count = 1;
  • step3:当数组大于零的时候并且当前遍历的值等于count的时候–count++
  • step4: 当遍历的数组元素已经大于count了,这时候退出循环,代表已经找到了对应的缺失的整数

代码

    int minNumberDisappeared(vector<int>& nums) {int count = 1;sort(nums.begin(), nums.end());for(auto num : nums){if(num > 0){if(count == num){count++;}else if(count < num){break;}}}return count;}

复杂度

时间复杂度:O( N l o g N NlogN NlogN) , 排序的时间复杂度近似为 N l o g N NlogN NlogN, 然后遍历了一遍数组

空间复杂度:O(1), 使用了常数个变量

方法二:哈希表

思路

step1:将数组中的所有元素全部放入到哈希表

step2:然后从1开始遍历哈希表不存在就结束

代码

    int minNumberDisappeared(vector<int>& nums) {unordered_map<int, int> hash;for(auto num : nums){hash[num]++;}int res = 1;while(hash[res]) res++;return res;}

复杂度

时间复杂度:O(N) , 遍历了一遍数组,然后遍历了部分哈希表

空间复杂度:O(N) , 使用了哈希表的额外空间

方法三:原地哈希

思路

  1. 数组长度和值范围
    • 一个长度为 n 的数组可以包含 n 个元素。
    • 如果数组中包含从 1 到 n* 的所有正整数,那么这 n* 个元素正好能填满整个数组。
  2. 最小的缺失正整数
    • 如果数组中包含了所有 1 到 n* 的数,那么下一个正整数就是 n+1。
    • 如果数组中缺少某个数,那么这个缺失的数一定在 1 到 n 之间。
  3. 极端情况
    • 如果数组中的数全部大于 n 或者非正(如 0 或负数),那么最小的缺失正整数就是 1,因为没有任何数在 1 到 n* 之间。

具体做法:

  • step 1:我们可以先遍历数组将所有的负数都修改成n+1。
  • step 2:然后再遍历数组,每当遇到一个元素绝对值不超过n时,则表示这个元素是1~n中出现的元素,我们可以将这个数值对应的下标里的元素改成负数,相当于每个出现过的正整数,我们把与它值相等的下标都指向一个负数,这就是类似哈希表的实现原理的操作。
  • step 3:最后遍历数组的时候碰到的第一个非负数,它的下标就是没有出现的第一个正整数,因为它在之前的过程中没有被修改,说明它这个下标对应的正整数没有出现过。

代码

int minNumberDisappeared(vector<int>& nums) {int n = nums.size();//遍历数组for(int i = 0; i < n; i++) //负数全部记为n+1if(nums[i] <= 0) nums[i] = n + 1;for(int i = 0; i < n; i++)//对于1-n中的数字if(abs(nums[i]) <= n) //这个数字的下标标记为负数nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]); for(int i = 0; i < n; i++)//找到第一个元素不为负数的下标if(nums[i] > 0)return i + 1;return n + 1;}

复杂度

从代码中可以看到,除了输入数组 nums 之外,算法没有使用额外的存储空间(只用了一些常数空间用于变量 in)。因此空间复杂度主要取决于输入数组。

由于算法就地(in-place)修改输入数组 nums,没有使用任何额外的存储空间,空间复杂度为 �(1)O(1)。

总结

  • 时间复杂度O(n)
  • 空间复杂度O(1)

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

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

相关文章

SPWM载波调制方式-三电平杂记1

方法一&#xff1a; P2 O1 N0 方法二&#xff1a;双载波直接发波 方法三&#xff1a;负轴载波和调制波往上抬升1&#xff0c;得到使用同一个载波 在正半周在P和O切换&#xff0c;在下半轴式O和N切换

出现 Transaction rolled back because it has been marked as rollback-only 解决方法

目录 1. 问题所示2. 原理分析3. 解决方法1. 问题所示 用户反馈的Bug如下所示: Transaction rolled back because it has been marked as rollback-only截图如下: 浏览器终端同样显示: 2. 原理分析 错误表明,在事务的生命周期内,遇到了某个异常或条件,导致该事务被标记…

四川古力未来科技抖音小店安全靠谱,购物新体验

在数字化浪潮席卷而来的今天&#xff0c;电商行业蓬勃发展&#xff0c;各种线上购物平台如雨后春笋般涌现。其中&#xff0c;抖音小店凭借其独特的短视频直播购物模式&#xff0c;迅速赢得了广大消费者的青睐。而四川古力未来科技抖音小店&#xff0c;更是以其安全靠谱、品质保…

注解的妙用

一、注解是什么&#xff1f; 在Java中&#xff0c;注解&#xff08;Annotation&#xff09;是一种用于在代码中插入元数据的方式。注解不直接影响程序代码的行为&#xff0c;而是提供了一种形式化的方法来说明代码的某些方面&#xff0c;供编译器、开发工具或运行时环境等使用…

Vue+AntDesignVue实现a-tree树形组件的层级选中功能

文章目录 一、构建树形组件二、js代码实现 最近碰到了一个新需求&#xff0c;使用树形选择器实现角色管理功能&#xff0c;当用户选中一个节点时&#xff0c;其所有子节点都会被自动选中&#xff1b;同样&#xff0c;当用户取消选中一个节点时&#xff0c;其所有子节点也会被取…

LNMP部署及应用

目录 1.LNMP概述 Nginx 特点 Nginx 作用 2.分布式部署LNMP操练 Nginx主机&#xff1a;CentOS 7-1 PHP主机: CentOS 7-2 1.LNMP概述 Nginx 是开源、高性能、高可靠的 Web 和反向代理服务器&#xff0c;而且支持热部署&#xff0c;几乎可以做到 7 * 24 小时不间断运行&…

Java实战:文本文件复制

任务目标 本实战任务的目标是创建一个Java程序&#xff0c;用于复制指定的文本文件到另一个位置&#xff0c;并在控制台中显示复制结果。 任务步骤 创建源文件&#xff1a;在指定的路径D:\love.txt创建源文件。创建文件复制类&#xff1a;在net.huawei.student.test包中创建…

绿联 安装memcached容器 - 一个开源的高性能分布式内存对象缓存系统

绿联 安装memcached容器 - 一个开源的高性能分布式内存对象缓存系统 1、镜像 memcached:latest 2、安装 2.1、基础设置 重启策略&#xff1a;容器退出时总是重启容器。 2.2、网络 网络选择桥接(bridge)。 2.3、端口设置 容器端口11211固定不变&#xff0c;本地端口若未被…

即时通讯视频会议平台,WorkPlus本地化部署解决方案

随着现代科技的快速发展&#xff0c;传统的会议方式已经不再满足企业和组织的需求。即时通讯视频会议以其便利性和高效性&#xff0c;成为了现代企业沟通和协作的重要工具。通过即时通讯视频会议&#xff0c;企业可以实现无时差的交流和远程协作&#xff0c;增强团队合作和提高…

计算机系统结构之虚拟存储器

虚拟存储器通过增设地址映像表机构来实现程序在主存中的定位。 一、段式管理 (1)段式管理的基本思想是把程序按内容或过程函数关系分成段&#xff0c;每段有自己的名字。一个用户作业或进程所包含的段对应一个二维线性虚拟空间&#xff08;二维虚拟存储器&#xff09;。段式管…

springboot实现文件上传功能,整合云服务

文章目录 这是springboot案例的,文件上传功能的拆分,本篇将带大家彻底了解文件上传功能,先从本地存储再到云存储,全网最详细版本,保证可以学会,可以了解文件上传功能的开发文件上传功能剖析进行书写一个小的文件上传文件上传的文件三要素首先表单提交的方式要是 post方式,第二个…

如何从Windows的硬盘中恢复丢失或删除的照片

你有没有不小心删除了一张你再也找不回来的重要照片&#xff1f;如果是您的公司或家庭照片、婚礼或童年回忆&#xff0c;或亲人的照片怎么办&#xff1f; 根据我们的经验&#xff0c;用户通常会在清理计算机的存储/速度时遇到这样的事故&#xff0c;并最终删除包含重要图片的文…

pytorch学习笔记5

transform 本质上作用是将图片通过transform这个这个工具箱获取想要的结果 tensor就是一个包含神经网络需要的一些理论基础的参数 from torch.utils.tensorboard import SummaryWriter from torchvision import transforms from PIL import Image #tensor数据类型 #通过tra…

最新h5st(4.7.2)参数分析与纯算法还原(含算法源码)

文章目录 1. 写在前面2. 加密分析3. 算法还原 【&#x1f3e0;作者主页】&#xff1a;吴秋霖 【&#x1f4bc;作者介绍】&#xff1a;擅长爬虫与JS加密逆向分析&#xff01;Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致力于Python…

22 、系统安全

新的服务器到手&#xff0c;部署服务器初始化。 1、配置ip地址 网关dns解析&#xff08;static&#xff09;内网和外网。 2、安装源&#xff0c;外网&#xff08;在线即可&#xff09;&#xff0c;内网&#xff08;只能用源码包编译安装&#xff09;。 3、磁盘分区&#xff…

k8s 1.28.x 配置nfs

1.安装nfs&#xff0c;在每个节点上安装 yum install -y nfs-utils 2.创建共享目录(主节点上操作) mkdir -p /opt/nfs/k8s 3.编写NFS的共享配置 /opt/nfs/k8s *(rw,no_root_squash) #*代表对所有IP都开放此目录&#xff0c;rw是读写 4.启动nfs systemctl enable nfs-ser…

十_信号11 - 函数sigsetjmp() 和 siglongjmp()

也就是说&#xff0c;正常情况下&#xff0c;当捕捉到一个信号&#xff0c;并调用该信号的信号处理程序时&#xff0c;被捕捉的信号会被加入到当前进程的信号屏蔽字中&#xff0c;以防止在本次信号处理程序还没有完成的时候&#xff0c;再次触发该信号&#xff0c; 发生重入。 …

Py列表(list)

目录 正向索引&#xff1a; 反向索引&#xff1a; 嵌套列表&#xff1a; 修改列表中的值 列表常用的方法 实例 练习&#xff1a; 正向索引&#xff1a; 从0开始&#xff0c;依次递增。第一个元素的索引为0&#xff0c;第二个元素的索引为1&#xff0c;依此类推。 列表的下标…

JS-09-es6常用知识1

目录 1 模板字符串 1.1 模板字符串基本用法 1.2 模板字符串解决了一些痛点 2 解构赋值 2.1 对象的解构赋值 2.2 函数参数的解构赋值 2.3 补写&#xff1a;属性的简写 3 rest参数 3.1 arguments 3.2 rest参数 3.3 补充&#xff1a;判断数据类型 4 箭头函数 4.1 …

传输中的串扰(八)

串扰指的是有害信号从一个线网传递到相邻线网上。通常把噪声源所在的线网称为动态线或攻击线网&#xff0c;而把有噪声形成的线网称为静态线或受害线网。 静态线上的噪声电压的表现与信号电压完全一样。一旦在静态线上产生噪声电压&#xff0c;它们就会传播并在阻抗突变处出现反…