当前位置: 首页 > news >正文

缺失的第一个正数:高效解法与技术

缺失的第一个正数:高效解法与技术

背景

在计算机编程中,有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题,并提供一个时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。

问题描述

leetcode 41.
给定一个未排序的整数数组 nums,需要找出其中没有出现的最小的正整数。

问题要求

这个问题的目标是寻找一个未排序的整数数组中没有出现的最小的正整数。具体要求如下:

  • 返回的结果必须是正整数,即大于等于1的整数。
  • 时间复杂度必须为O(n),其中n是数组的长度。
  • 额外空间复杂度必须是常数级别。

示例 1:

输入:nums = [1,2,0]
输出:3

示例 2:

输入:nums = [3,4,-1,1]
输出:2

解决思路

为了解决这个问题,我们可以利用数组本身来存储信息,以便找到缺失的最小正整数。解决思路可以分为以下步骤:

  1. 将正整数移动到正确的位置: 首先,我们需要遍历数组 nums,将正整数移动到正确的位置。具体来说,我们将正整数 x 移动到数组的第 x-1 个位置,因为最小的正整数一定在 1n+1 的范围内,其中 n 是数组的长度。

  2. 找到第一个不在正确位置的整数: 接下来,我们再次遍历数组 nums,找到第一个不在正确位置的整数。这个整数的索引加一即为缺失的最小正整数。

  3. 如果整个数组都在正确位置: 如果整个数组都在正确位置,即 nums[i] == i + 1,那么缺失的最小正整数是 n + 1

优化思路

在上述解决思路的基础上,可以进一步优化算法,以满足时间复杂度和空间复杂度的要求。以下是一些优化思路:

  1. 避免重复交换操作: 在重新排列数组时,可以避免多次重复交换元素的操作,以提高效率。可以使用一个循环来将正整数移动到正确的位置,而不是每次都交换两个元素。

  2. 避免对负数和大于数组长度的正整数进行处理: 因为负数和大于数组长度的正整数不会影响最小正整数的计算,可以跳过对它们的处理。

代码实现

以下是使用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)是一种排序算法,它通过将数据分割成若干个有限数量的桶(或箱子),然后分别对每个桶内的数据进行排序,最后合并所有桶的结果,得到有序序列。桶排序通常适用于对一定范围内的数据进行排序,特别是适用于对非常大的数据集合进行排序。下面是一些与桶排序相关的知识和要点:

工作原理

桶排序的工作原理可以概括为以下几个步骤:

  1. 分桶: 将数据划分成若干个桶,每个桶负责一定范围的数据。桶的数量可以根据数据的分布情况来确定。

  2. 桶内排序: 对每个桶内的数据进行排序。这可以使用任何其他排序算法,通常选择的是快速排序或插入排序等。

  3. 合并: 将所有桶的数据按照顺序合并起来,得到最终的有序序列。

适用场景

桶排序适用于一定范围内的数据集合,特别是对均匀分布的数据排序效果最好。它在以下情况下特别有优势:

  • 当数据分布相对均匀,且数据范围已知时,桶排序可以快速得到有序结果。

  • 桶排序可以并行化处理,因为每个桶可以独立排序,然后合并。

  • 当数据范围较小但数据量较大时,桶排序可以提高排序的速度。

时间复杂度

桶排序的时间复杂度取决于桶的数量和桶内排序所用的时间。假设有 n 个元素和 k 个桶:

  • 如果桶的数量 k 近似于 n,即每个桶只包含一个元素,那么桶排序的时间复杂度接近于 O(n^2),类似于插入排序。

  • 如果桶的数量 k 近似于 1,即所有元素都放在一个桶内,那么桶排序的时间复杂度接近于 O(nlogn),类似于快速排序。

  • 通常情况下,桶排序的时间复杂度为 O(n + k),其中 k 取决于数据的分布情况和桶的数量。

稳定性

桶排序通常是稳定的,也就是说,具有相同值的元素在排序后的相对位置不会发生改变。

桶排序的限制

桶排序的效率受到数据分布情况的影响,如果数据分布非常不均匀,导致大部分数据集中在一个或少数几个桶内,那么桶排序的效率可能会下降。

此外,桶排序需要额外的内存空间来存储桶,因此在数据量非常大时,可能会占用大量内存。

总之,桶排序是一种高效的排序算法,特别适用于数据分布均匀、范围已知的情况。在实际应用中,可以根据数据的特点来选择合适的桶排序算法参数,以获得最佳的性能。

相关文章:

缺失的第一个正数:高效解法与技术

缺失的第一个正数&#xff1a;高效解法与技术 背景 在计算机编程中&#xff0c;有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题&#xff0c;并提供一个时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。 问题描述 leet…...

常用的辅助网站(持续更新)

标题 一、uni-app方向二、H5方向 一、uni-app方向 1、uni-app官网 地址&#xff1a;https://uniapp.dcloud.net.cn/ 2、香蕉云编 地址&#xff1a;https://www.yunedit.com/ 描述&#xff1a;一般用来配置ios证书或安卓证书、上传ios包至商店 3、uView 地址&#xff1a;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{}{}}// 将结果设置为一个最大值&#xff0c;防止影响求最小值的逻辑res : ma…...

每日一题:请解释什么是闭包(Closure)?并举一个实际的例子来说明。(前端初级)

今天继续在前端初级笔试题中被AI虐&#xff1a; 碱面的答案&#xff0c;问题&#xff1a;初级&#xff0c;回答&#xff1a;初级https://bs.rongapi.cn/1702510598371151872/14我的回答如下&#xff1a; 闭包是指由大括号包裹的一个区域&#xff0c;这个区域代表了一个变量生效…...

广告主必看!NetMarvel五大优势驱动出海App投放增长

App出海走到今天&#xff0c;流量红利早就不存在&#xff0c;摆在广告主面前最棘手的两个问题&#xff0c;一是不起量&#xff0c;二是买量成本太高&#xff0c;得不偿失。 如何在确保出海应用用户规模有所增长的同时&#xff0c;也保证整体ROI处在较高水平&#xff1f;NetMar…...

数据结构与算法之复杂度

时间复杂度 1.抓大头 2.常数用o(1),低阶函数也用o(1)代替&#xff08;直接去掉&#xff09; 3.取最坏情况 对数相关写法的规定...

ATECLOUD电源测试软件平台如何测试电源纹波?

电源纹波是影响电源稳定性的重要因素&#xff0c;过大的纹波会导致电源模块的工作效率降低&#xff0c;可能使电源模块直接损坏。使用ATECLOUD碘盐测试软件平台对纹波进行测试&#xff0c;检测其工作情况&#xff0c;以确保其稳定性和性能。 电源纹波的产生 电源的纹波通俗的来…...

数据结构与算法:排序算法(2)

目录 堆排序 使用步骤 代码实现 计数排序 适用范围 过程 代码实现 排序优化 桶排序 工作原理 代码实现 堆排序 二叉堆的特性&#xff1a; 1. 最大堆的堆顶是整个堆中的最大元素 2. 最小堆的堆顶是整个堆中的最小元素 以最大堆为例&#xff0c;如果删除一个最大堆的…...

1_图神经网络GNN基础知识学习

文章目录 安装PyTorch Geometric安装工具包 在KarateClub数据集上使用图卷积网络 (GCN) 进行节点分类两个画图函数Graph Neural Networks数据集&#xff1a;Zacharys karate club network.PyTorch Geometric数据集介绍 edge_index使用networkx可视化展示 Graph Neural Networks…...

瑞芯微:基于RK3568的ocr识别

光学字符识别&#xff08;Optical Character Recognition, OCR&#xff09;是指对文本资料的图像文件进行分析识别处理&#xff0c;获取文字及版面信息的过程。亦即将图像中的文字进行识别&#xff0c;并以文本的形式返回。OCR的应用场景 卡片证件识别类&#xff1a;大陆、港澳…...

C++真的是 C加加

&#x1f4dd;个人主页&#xff1a;夏目浅石. &#x1f4cc;博客专栏&#xff1a;C的故事 &#x1f3e0;学习社区&#xff1a;夏目友人帐. 文章目录 前言Ⅰ. 函数重载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生成的单文档应用程序中&#xff0c;主框架类和视类均具有PreCreateWindow函数&#xff1b; 从名字可知&#xff0c;可在此函数中添加一些代码&#xff0c;来控制窗口显示后的效果&#xff1b; 并且它有注释说明&#xff0c; Modify the Window class or styles here by…...

for forin forof forEach map区别

一、总结 相同点&#xff1a;都是串行遍历。不同点&#xff1a; 二、for of循环 设计目的&#xff1a;遍历所有数据结构的统一方法。原理&#xff1a;会调用数据结构的Symbol.iterator方法。 只要数据结构定义了Symbol.iterator属性&#xff0c;就能用for of遍历它的成员。…...

特殊时间(蓝桥杯)

特殊时间 问题描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 2022年2月22日22:20 是一个很有意义的时间, 年份为 2022 , 由 3 个 2 和 1 个 0 组成, 如果将月和日写成 4 位, 为 0222 , 也是由 3 个 2 和 1 个 0 组 成…...

VUE路由与nodeJS环境搭建

VUE路由 Vue路由是Vue.js提供的路由管理工具&#xff0c;它允许我们在应用程序中实现页面之间的导航&#xff0c;从而使单页面应用程序的开发更加方便。通过Vue路由&#xff0c;我们可以轻松地创建和管理多个视图&#xff0c;并在这些视图之间导航。 Vue路由使用HTML5的Histo…...

抗锯齿的线

抗锯齿的线 右下角的时候h是0,到顶部 h是1&#xff0c;然后中间y相距4个像素&#xff0c;那dy就是0.25 如果让h abs(fract(h - 0.5) - 0.5) 中间一行0.5&#xff0c;第一行 第三行都是0.25&#xff0c;两端都是0 根据插值来看 这里是 如果用h/dy 那么第一行以上&#xff0…...

如何使用高压放大器驱动高容性负载

使用高压放大器驱动高容性负载是一个具有挑战性的任务&#xff0c;需要仔细考虑电路设计和操作技巧。下面西安安泰Aigtek将为您介绍一些关于如何使用高压放大器驱动高容性负载的方法和注意事项。 首先&#xff0c;让我们了解一下高容性负载。高容性负载通常指电容值较大的负载元…...

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的日志&#xff0c;报错信息如下 {"level&…...

nvm使用的注意事项和常用命令。

nvm官网下载地址&#xff1a;nvm文档手册 - nvm是一个nodejs版本管理工具 - nvm中文网 (uihtm.com) 参考网址&#xff1a;(14 封私信 / 80 条消息) 如何通过 nvm 安装多版本 nodejs&#xff1f;npm 安装失败了怎么办&#xff1f; - 知乎 (zhihu.com) nvm目录下&#xff0c;修…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...