缺失的第一个正数:高效解法与技术
缺失的第一个正数:高效解法与技术
背景
在计算机编程中,有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题,并提供一个时间复杂度为 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目录下,修…...

练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...

k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...