缺失的第一个正数:高效解法与技术
缺失的第一个正数:高效解法与技术
背景
在计算机编程中,有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题,并提供一个时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。
问题描述
leetcode 41.
给定一个未排序的整数数组 nums
,需要找出其中没有出现的最小的正整数。
问题要求
这个问题的目标是寻找一个未排序的整数数组中没有出现的最小的正整数。具体要求如下:
- 返回的结果必须是正整数,即大于等于1的整数。
- 时间复杂度必须为O(n),其中n是数组的长度。
- 额外空间复杂度必须是常数级别。
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
解决思路
为了解决这个问题,我们可以利用数组本身来存储信息,以便找到缺失的最小正整数。解决思路可以分为以下步骤:
-
将正整数移动到正确的位置: 首先,我们需要遍历数组
nums
,将正整数移动到正确的位置。具体来说,我们将正整数x
移动到数组的第x-1
个位置,因为最小的正整数一定在1
到n+1
的范围内,其中n
是数组的长度。 -
找到第一个不在正确位置的整数: 接下来,我们再次遍历数组
nums
,找到第一个不在正确位置的整数。这个整数的索引加一即为缺失的最小正整数。 -
如果整个数组都在正确位置: 如果整个数组都在正确位置,即
nums[i] == i + 1
,那么缺失的最小正整数是n + 1
。
优化思路
在上述解决思路的基础上,可以进一步优化算法,以满足时间复杂度和空间复杂度的要求。以下是一些优化思路:
-
避免重复交换操作: 在重新排列数组时,可以避免多次重复交换元素的操作,以提高效率。可以使用一个循环来将正整数移动到正确的位置,而不是每次都交换两个元素。
-
避免对负数和大于数组长度的正整数进行处理: 因为负数和大于数组长度的正整数不会影响最小正整数的计算,可以跳过对它们的处理。
代码实现
以下是使用Python编写的代码,实现了上述解决思路:
class Solution:def firstMissingPositive(self, nums):if nums is None or len(nums) == 0:return 1n = len(nums)# 第一次遍历:将正整数移动到正确的位置for i in range(n):while 0 < nums[i] < n and nums[nums[i]-1] != nums[i]:# 将正整数 nums[i] 移动到位置 nums[i]-1temp = nums[nums[i]-1]nums[nums[i]-1] = nums[i]nums[i] = temp# 第二次遍历:找到第一个位置不匹配的元素for i in range(n):if nums[i] != i+1:# 返回缺失的最小正整数return i+1# 如果整个数组都在正确位置,返回 n+1return n+1
时间复杂度分析
这个算法只需要两次遍历数组,因此时间复杂度是 O(n),其中 n 是数组的长度。由于只使用常数级别额外空间,这个算法在空间复杂度上也是非常高效的。
结论
寻找缺失的第一个正数是一个有趣的编程问题,通过巧妙地使用数组本身,我们可以在时间复杂度为 O(n) 的情况下找到答案。这种技巧在实际编程中非常有用,特别是在需要满足空间复杂度限制的情况下。理解这个问题的解决思路和技术背景对于编程中的实际问题非常有帮助。希望这篇博客能够帮助你更好地理解和解决缺失的第一个正数问题。
相关知识(桶排序)
桶排序(Bucket Sort)是一种排序算法,它通过将数据分割成若干个有限数量的桶(或箱子),然后分别对每个桶内的数据进行排序,最后合并所有桶的结果,得到有序序列。桶排序通常适用于对一定范围内的数据进行排序,特别是适用于对非常大的数据集合进行排序。下面是一些与桶排序相关的知识和要点:
工作原理
桶排序的工作原理可以概括为以下几个步骤:
-
分桶: 将数据划分成若干个桶,每个桶负责一定范围的数据。桶的数量可以根据数据的分布情况来确定。
-
桶内排序: 对每个桶内的数据进行排序。这可以使用任何其他排序算法,通常选择的是快速排序或插入排序等。
-
合并: 将所有桶的数据按照顺序合并起来,得到最终的有序序列。
适用场景
桶排序适用于一定范围内的数据集合,特别是对均匀分布的数据排序效果最好。它在以下情况下特别有优势:
-
当数据分布相对均匀,且数据范围已知时,桶排序可以快速得到有序结果。
-
桶排序可以并行化处理,因为每个桶可以独立排序,然后合并。
-
当数据范围较小但数据量较大时,桶排序可以提高排序的速度。
时间复杂度
桶排序的时间复杂度取决于桶的数量和桶内排序所用的时间。假设有 n 个元素和 k 个桶:
-
如果桶的数量 k 近似于 n,即每个桶只包含一个元素,那么桶排序的时间复杂度接近于 O(n^2),类似于插入排序。
-
如果桶的数量 k 近似于 1,即所有元素都放在一个桶内,那么桶排序的时间复杂度接近于 O(nlogn),类似于快速排序。
-
通常情况下,桶排序的时间复杂度为 O(n + k),其中 k 取决于数据的分布情况和桶的数量。
稳定性
桶排序通常是稳定的,也就是说,具有相同值的元素在排序后的相对位置不会发生改变。
桶排序的限制
桶排序的效率受到数据分布情况的影响,如果数据分布非常不均匀,导致大部分数据集中在一个或少数几个桶内,那么桶排序的效率可能会下降。
此外,桶排序需要额外的内存空间来存储桶,因此在数据量非常大时,可能会占用大量内存。
总之,桶排序是一种高效的排序算法,特别适用于数据分布均匀、范围已知的情况。在实际应用中,可以根据数据的特点来选择合适的桶排序算法参数,以获得最佳的性能。
相关文章:
缺失的第一个正数:高效解法与技术
缺失的第一个正数:高效解法与技术 背景 在计算机编程中,有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题,并提供一个时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。 问题描述 leet…...
常用的辅助网站(持续更新)
标题 一、uni-app方向二、H5方向 一、uni-app方向 1、uni-app官网 地址:https://uniapp.dcloud.net.cn/ 2、香蕉云编 地址:https://www.yunedit.com/ 描述:一般用来配置ios证书或安卓证书、上传ios包至商店 3、uView 地址:http…...
LeetCode 75 - 01 : 最小面积矩形
type pair struct{x, y int }func minAreaRect(points [][]int)int{mp : map[pair]struct{}{}// 将二维数组中的坐标映射到map中for i : range points{mp[pair{points[i][0], points[i][1]}] struct{}{}}// 将结果设置为一个最大值,防止影响求最小值的逻辑res : ma…...
每日一题:请解释什么是闭包(Closure)?并举一个实际的例子来说明。(前端初级)
今天继续在前端初级笔试题中被AI虐: 碱面的答案,问题:初级,回答:初级https://bs.rongapi.cn/1702510598371151872/14我的回答如下: 闭包是指由大括号包裹的一个区域,这个区域代表了一个变量生效…...
广告主必看!NetMarvel五大优势驱动出海App投放增长
App出海走到今天,流量红利早就不存在,摆在广告主面前最棘手的两个问题,一是不起量,二是买量成本太高,得不偿失。 如何在确保出海应用用户规模有所增长的同时,也保证整体ROI处在较高水平?NetMar…...
数据结构与算法之复杂度
时间复杂度 1.抓大头 2.常数用o(1),低阶函数也用o(1)代替(直接去掉) 3.取最坏情况 对数相关写法的规定...
ATECLOUD电源测试软件平台如何测试电源纹波?
电源纹波是影响电源稳定性的重要因素,过大的纹波会导致电源模块的工作效率降低,可能使电源模块直接损坏。使用ATECLOUD碘盐测试软件平台对纹波进行测试,检测其工作情况,以确保其稳定性和性能。 电源纹波的产生 电源的纹波通俗的来…...
数据结构与算法:排序算法(2)
目录 堆排序 使用步骤 代码实现 计数排序 适用范围 过程 代码实现 排序优化 桶排序 工作原理 代码实现 堆排序 二叉堆的特性: 1. 最大堆的堆顶是整个堆中的最大元素 2. 最小堆的堆顶是整个堆中的最小元素 以最大堆为例,如果删除一个最大堆的…...
1_图神经网络GNN基础知识学习
文章目录 安装PyTorch Geometric安装工具包 在KarateClub数据集上使用图卷积网络 (GCN) 进行节点分类两个画图函数Graph Neural Networks数据集:Zacharys karate club network.PyTorch Geometric数据集介绍 edge_index使用networkx可视化展示 Graph Neural Networks…...
瑞芯微:基于RK3568的ocr识别
光学字符识别(Optical Character Recognition, OCR)是指对文本资料的图像文件进行分析识别处理,获取文字及版面信息的过程。亦即将图像中的文字进行识别,并以文本的形式返回。OCR的应用场景 卡片证件识别类:大陆、港澳…...
C++真的是 C加加
📝个人主页:夏目浅石. 📌博客专栏:C的故事 🏠学习社区:夏目友人帐. 文章目录 前言Ⅰ. 函数重载0x00 重载规则0x01 函数重载的原理名字修饰 Ⅱ. 引用0x00 引用的概念0x01 引用和指针区分0x03 引用的本质0x04…...
java学习--day5 (java中的方法、break/continue关键字)
文章目录 day4作业今天的内容1.方法【重点】1.1为什么要有方法1.2其实已经见过方法1.3定义方法的语法格式1.3.1无参无返回值的方法1.3.2有参无返回值的方法1.3.3无参有返回值的方法1.3.4有参有返回值的方法 2.break和continue关键字2.1break;2.2continue; 3.案例关于方法的练习…...
MFC主框架和视类PreCreateWindow()函数学习
在VC生成的单文档应用程序中,主框架类和视类均具有PreCreateWindow函数; 从名字可知,可在此函数中添加一些代码,来控制窗口显示后的效果; 并且它有注释说明, Modify the Window class or styles here by…...
for forin forof forEach map区别
一、总结 相同点:都是串行遍历。不同点: 二、for of循环 设计目的:遍历所有数据结构的统一方法。原理:会调用数据结构的Symbol.iterator方法。 只要数据结构定义了Symbol.iterator属性,就能用for of遍历它的成员。…...
特殊时间(蓝桥杯)
特殊时间 问题描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 2022年2月22日22:20 是一个很有意义的时间, 年份为 2022 , 由 3 个 2 和 1 个 0 组成, 如果将月和日写成 4 位, 为 0222 , 也是由 3 个 2 和 1 个 0 组 成…...
VUE路由与nodeJS环境搭建
VUE路由 Vue路由是Vue.js提供的路由管理工具,它允许我们在应用程序中实现页面之间的导航,从而使单页面应用程序的开发更加方便。通过Vue路由,我们可以轻松地创建和管理多个视图,并在这些视图之间导航。 Vue路由使用HTML5的Histo…...
抗锯齿的线
抗锯齿的线 右下角的时候h是0,到顶部 h是1,然后中间y相距4个像素,那dy就是0.25 如果让h abs(fract(h - 0.5) - 0.5) 中间一行0.5,第一行 第三行都是0.25,两端都是0 根据插值来看 这里是 如果用h/dy 那么第一行以上࿰…...
如何使用高压放大器驱动高容性负载
使用高压放大器驱动高容性负载是一个具有挑战性的任务,需要仔细考虑电路设计和操作技巧。下面西安安泰Aigtek将为您介绍一些关于如何使用高压放大器驱动高容性负载的方法和注意事项。 首先,让我们了解一下高容性负载。高容性负载通常指电容值较大的负载元…...
kubernetes集群证书过期启动失败问题解决方法
1、问题现象 执行kubectl命令异常报告 [rootk8s-master1 ~]# kubectl get node The connection to the server 192.168.227.131:6443 was refused - did you specify the right host or port? [rootk8s-master1 ~]# 查看etcd的日志,报错信息如下 {"level&…...
nvm使用的注意事项和常用命令。
nvm官网下载地址:nvm文档手册 - nvm是一个nodejs版本管理工具 - nvm中文网 (uihtm.com) 参考网址:(14 封私信 / 80 条消息) 如何通过 nvm 安装多版本 nodejs?npm 安装失败了怎么办? - 知乎 (zhihu.com) nvm目录下,修…...
代码大全阅读随笔(七)
循环控制 循环控制会出现什么样的错误,任何一种答案都可以归结到下面所说的问题之一:忽略或者错误的对循环执行初始化,忽略了对累加变量或者其他与循环有关变量执行初始化,不正确的嵌套,不正确的循环终止,忽…...
用户与权限管理
文章目录 用户与权限管理1. 用户管理1.1 MYSQL用户1.2 登录MySQL服务器1.3 创建用户1.4 修改用户1.5 删除用户1.6 修改密码1. 修改当前用户密码2. 修改其他用户密码 1.7 MYSQL8密码管理 2. 权限管理2.1 权限列表2.2 授予权限的原则2.3 授予权限2.4 查看权限2.5 收回权限 3. 权限…...
mysql集群使用nginx配置负载均衡
参考链接:https://mu-sl.com//archives/mysql%E9%9B%86%E7%BE%A4%E4%BD%BF%E7%94%A8nginx%E9%85%8D%E7%BD%AE%E8%B4%9F%E8%BD%BD%E5%9D%87%E8%A1%A1 配置文件nginx_tcp.conf 示例 load_module modules/ngx_stream_module.so;stream{upstream tcpssh{hash $remote_…...
蓝桥杯每日一题2023.9.21
蓝桥杯2021年第十二届省赛真题-异或数列 - C语言网 (dotcpp.com) 题目描述 Alice 和 Bob 正在玩一个异或数列的游戏。初始时,Alice 和 Bob 分别有一个整数 a 和 b,有一个给定的长度为 n 的公共数列 X1, X2, , Xn。 Alice 和 Bob 轮流操作࿰…...
知识联合——函数指针数组
前言:小伙伴们又见面啦,今天我们来讲解一个将函数,指针,数组这三个C语言大将整合在一起的知识——函数指针数组。同时来告诉小伙伴们我们上一篇文章的伏笔——函数指针的具体用法。 目录 一.什么是函数指针数组 二.函数指针数组…...
【Nginx26】Nginx学习:日志与镜像流量复制
Nginx学习:日志与镜像流量复制 总算到了日志模块,其实这个模块的指令之前我们就用过了,而且也是是非常常见的指令。相信这一块的学习大家应该不会有什么难度。另一个则是镜像功能,这个估计用过的同学就比较少了,不过也…...
Stability AI发布基于稳定扩散的音频生成模型Stable Audio
近日Stability AI推出了一款名为Stable Audio的尖端生成模型,该模型可以根据用户提供的文本提示来创建音乐。在NVIDIA A100 GPU上Stable Audio可以在一秒钟内以44.1 kHz的采样率产生95秒的立体声音频,与原始录音相比,该模型处理时间的大幅减少…...
华为OD机试 - 计算面积 - 逻辑分析(Java 2023 B卷 100分)
目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中,刷题点这里 专栏导读 本专栏收录于《华为OD机试(JAVA)真题(A卷B卷&#…...
Ganache本地测试网+cpolar内网穿透实现公网访问内网
文章目录 前言1. 本地环境服务搭建2. 局域网测试访问3. 内网穿透3.1 ubuntu本地安装cpolar内网穿透3.2 创建隧道3.3 测试公网访问 4. 配置固定二级子域名4.1 保留一个二级子域名4.2 配置二级子域名4.3 测试访问公网固定二级子域名 前言 网:我们通常说的是互联网&am…...
【每日一题】ARC071D - ### | 前缀和 | 简单
题目内容 原题链接 给定一个长度为 n n n 的数组 a a a 和一个长度为 m m m 的数组 b b b 。 从数组 a a a 中挑出两个数,作为两条平行于 y y y 轴的直线,数组 b b b 中挑出两个数,作为两条平行于 x x x 轴的直线,问这四…...
威海网站建设公司/搜狗关键词排名此会zjkwlgs
目录 1、Map接口的定义 2、HashMap子类 3、Hashtable子类(旧的子类) 4、排序的子类:TreeMap 5、利用Iterator输出Map集合 6、自定义Map中的key 7、总结 1、Map接口的定义 Map保存的是二元偶对象,简单说就是两个值…...
衢州网站公司/seo优化中商品权重主要由什么决定
烤瓷牙可真是种类繁多,种类主要分为金属烤瓷牙和全瓷烤瓷牙两大类。金属烤瓷牙分为非贵金属烤瓷牙、半贵金属烤瓷牙、贵金属烤瓷牙和钛及钛合金烤瓷牙。其中非贵金属烤瓷牙又被分为全瓷釉瓷贴面、全瓷冠、烤瓷冠。 1.镍铬合金 较早的烤瓷牙多用镍铬合金,…...
做网站公司需要什么资质/营销软件站
前言 DLL,即Dynamic-link library,动态链接库。关于其详细介绍,参阅:https://en.wikipedia.org/wiki/Dynamic-link_library 创建一个DLL 声明导出函数:extern “C” __declspec(dllexport) int add(int a, int b);其中…...
湖南网站建设/各城市首轮感染高峰期预测
Swift标准库可以编译安卓armv7的内核,这使得可以在安卓移动设备上执行Swift语句代码。本文解释了如何在你的安卓手机上运行一个简单的“hello,world”程序。如果你遇到了任何问题,请参考下面的说明,上传BUG到 https://bugs.swift.…...
网页建站网站申请/广告联盟app下载
讨人喜欢的26个原则,让你的人际关系更上一层楼! 1.长相不令人讨厌,如果长得不好,就让自己有才气;如果才气也没有,那就总是微笑。 2.气质是关键。如果时尚学不好,宁愿纯朴。 …...
建设网站域名备案查询/安卓优化大师历史版本
当今市场上手机的种类多如牛毛,基本功能都是打电话和发短信,然后,如果是我们生产一款手机,怎样才能让我们的手机拥有自己的卖点,在手机市场上脱颖而出,赢得消费者的青睐呢?我觉得非常重要的一点…...