给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数
这个算法的核心思想是通过交换操作,将每个数放到它应该在的位置上。然后再次遍历数组,找到第一个不在正确位置上的数,其索引加一即为缺失的最小正整数。
def first_missing_positive(nums):n = len(nums)# 第一次遍历,将数组中的每个数放到正确的位置上for i in range(n):while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]# 第二次遍历,找到第一个不在正确位置上的数,即为缺失的最小正整数for i in range(n):if nums[i] != i + 1:return i + 1# 如果数组中所有数都在正确位置上,则缺失的是数组长度+1return n + 1
这个算法的时间复杂度是 O(n),因为每个数最多进行两次交换操作,而且只进行了两次遍历。额外空间复杂度是 O(1),因为只使用了常数级别的额外空间。
原地哈希算法的原理是通过修改输入数据本身,将数据映射到正确的位置上,从而完成一些特定的操作。在具体的场景中,原地哈希算法通常用于解决一些空间复杂度受限制的问题,以达到在常数级别的额外空间内完成操作的目的。
for i in range(n):while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
-
在这一步中,如果 nums[i] 不在正确的位置上,并且它应该在的位置上的数不等于它,就进行交换。
-
第二次遍历:找到第一个不在正确位置上的数,即为缺失的最小正整数。
-
for i in range(n):
if nums[i] != i + 1:
return i + 1
在这一步中,如果 nums[i] 不等于 i + 1,说明 i + 1 是缺失的最小正整数。
这样,通过两次遍历和原地交换的方式,就可以在常数级别的额外空间内找到未排序整数数组中缺失的最小正整数。
原地哈希算法通常涉及到将数据按某种规则重新排列,以满足问题的要求,而不需要额外的数据结构来存储中间结果。
相关文章:
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数
这个算法的核心思想是通过交换操作,将每个数放到它应该在的位置上。然后再次遍历数组,找到第一个不在正确位置上的数,其索引加一即为缺失的最小正整数。 def first_missing_positive(nums):n len(nums)# 第一次遍历,将数组中的每…...
C#使用RabbitMQ-4_路由模式(直连交换机)
简介 RabbitMQ中的路由模式是一种根据Routing Key有条件地将消息筛选后发送给消费者的模式。在路由模式中,生产者向交换机发送消息时,会指定一个Routing Key。交换机接收生产者的消息后,根据消息的Routing Key将其路由到与Routing Key完全匹…...
PyTorch 之 nn.Parameter
文章目录 使用方法:为什么使用 nn.Parameter:示例使用: 在 PyTorch 中,nn.Parameter 是一个类,用于将张量包装成可学习的参数。它是 torch.Tensor 的子类,但被设计成可以被优化器更新的参数。通过将张量包装…...
KAFKA高可用架构涉及常用功能整理
KAFKA高可用架构涉及常用功能整理 1. kafka的高可用系统架构和相关组件2. kafka的核心参数2.1 常规配置2.2 特殊优化配置 3. kafka常用命令3.1 常用基础命令3.1.1 创建topic3.1.2 获取集群的topic列表3.1.3 获取集群的topic详情3.1.4 删除集群的topic3.1.5 获取集群的消费组列表…...
3d模型上的材质怎么删除---模大狮模型网
在大多数3D软件中,可以通过以下步骤来删除3D模型上的材质: 选择要删除材质的模型:首先,从场景中选择包含目标材质的模型。可以使用选择工具或按名称查找模型。 进入编辑模式:将模型切换到编辑模式。这通常需要选择相应…...
leetcode hot100跳跃游戏Ⅱ
本题和上一题还是有不一样的地方,这个题中,我们需要记录我们跳跃的步数并尽可能的满足最小的跳跃步数到达终点。 那么我们还是采用覆盖范围的概念,但是我们需要两个,一个是在当前位置的覆盖范围,另一个是下一步的覆盖…...
大数据期望最大化(EM)算法:从理论到实战全解析
文章目录 大数据期望最大化(EM)算法:从理论到实战全解析一、引言概率模型与隐变量极大似然估计(MLE)Jensen不等式 二、基础数学原理条件概率与联合概率似然函数Kullback-Leibler散度贝叶斯推断 三、EM算法的核心思想期…...
【鸿蒙】大模型对话应用(二):对话界面设计与实现
Demo介绍 本demo对接阿里云和百度的大模型API,实现一个简单的对话应用。 DecEco Studio版本:DevEco Studio 3.1.1 Release HarmonyOS SDK版本:API9 关键点:ArkTS、ArkUI、UIAbility、网络http请求、列表布局、层叠布局 对话页…...
MySQL 导入数据
我们可以将已有的数据导入到MySQL数据库中,下面是几种方式: 1、mysql 命令导入 使用 mysql 命令导入语法格式为: mysql -u用户名 -p密码 < 要导入的数据库数据(shulanxt.sql) 实例: # mysql -uroot -p123456 < …...
探索数字经济:从基础到前沿的奇妙旅程
新一轮技术革命方兴未艾,特别是以人工智能、大数据、物联网等为代表的数字技术革命,催生了一系列新技术、新产业、新模式,深刻改变着世界经济面貌。数字经济已成为重组全球要素资源、重塑全球经济结构、改变全球竞争格局的关键力量。预估到20…...
【INTEL(ALTERA)】如何在 Windows 操作系统上设置 Design Space Explorer II 远程 SSH 场
说明 从英特尔 Quartus Prime Pro Edition 软件 22.1 版本开始,您可以选择使用 Windows OpenSSH 服务器设置 Design Space Explorer II (DSE II)。 解决方法 1.让 DSE II 与 OpenSSH 协同工作的第一步是 安装 OpenSSH。应在远程主机上安装 Op…...
Python编程-使用urllib进行网络爬虫常用内容梳理
Python编程-使用urllib进行网络爬虫常用内容梳理 使用urllib库进行基础网络请求 使用request发起网络请求 from urllib import request from http.client import HTTPResponseresponse: HTTPResponse request.urlopen(url"http://pkc/vul/sqli/sqli_str.php") pr…...
01 Redis的特性+下载安装启动+Redis自动启动+客户端连接
1.1 NoSQL NoSQL(“non-relational”, “Not Only SQL”),泛指非关系型的数据库。 键值存储数据库 : 就像 Map 一样的 key-value 对。如Redis文档数据库 : NoSQL 与关系型数据的结合,最像关系…...
C++发起Https请求
Wininet库忽略Https证书 相信很多朋友使用C WINAPI开发的时候网络模块的时候遇到Https忽悠证书无效的情况下, 仍然希望获取结果下列代码便是忽略异常的Https CA证书,下面对原理进行简单的讲解首先, 需要设置Https忽略需要用到如下结果函数与参数Interne…...
哪款笔记软件支持电脑和手机互通数据?
上班族在日常工作中,随手记录工作笔记已成为司空见惯的场景。例如:从快节奏的会议记录到灵感迸发的创意;跟踪项目进展,记录每个阶段的成果、问题和下一步计划;记录、更新工作任务清单等,工作笔记承载了职场…...
部署PXE高效批量网络装机
部署PXE高效批量网络装机 因在Cisco3850核心交换机中已开启DHCP 服务,因此不需要在配置DHCP服务。如果您的网络环境中也已有DHCP服务,也不用再配置DHCP服务了,直接部署PXE相关服务即可。 找一台linux系统的服务器,这本次试验用的是…...
【JavaEE】UDP协议与TCP协议
作者主页:paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文于《JavaEE》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造&…...
Leetcode—1828. 统计一个圆中点的数目【中等】
2024每日刷题(一零五) Leetcode—1828. 统计一个圆中点的数目 实现代码 class Solution { public:vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {vector<int> a…...
新概念英语第二册(47)
New words and expressions】生词和短语(9) thirsty adj. 贪杯的 ghost n. 鬼魂 haunt v. (鬼)来访,闹鬼 block …...
抽象类(Java)、模板方法设计模式
一、概念 在Java中有abstract关键字,就是抽象的意思,可用来修饰类和成员方法。 用abstract来修饰类,那这个类就是抽象类;修饰方法,那这个方法就是抽象方法。 修饰符 abstract class 类名{修饰符 abstract 返回值类型…...
《B3845 [GESP样题 二级] 勾股数》
题目背景 对应的选择、判断题:https://ti.luogu.com.cn/problemset/1102 题目描述 勾股数是很有趣的数学概念。如果三个正整数 a,b,c,满足 a2b2c2,而且 1≤a≤b≤c,我们就将 a,b,c 组成的三元组 (a,b,c) 称为勾股数。你能通过编…...
Ubuntu 24.04 内核 Kernel Panic 问题排查与解决流程(第二次出现该问题后,永久性解决)
问题描述 系统更新后重启,出现以下错误: Kernel panic - not syncing: VFS: Unable to mount root fs on unknown-block(0,0)系统无法正常启动。问题原因分析 错误含义 内核在启动过程中无法找到并挂载根文件系统。unknown-block(0,0) 表示内核完全不知道…...
Open-Shell-Menu:让Windows界面回归高效与个性化的开源解决方案
Open-Shell-Menu:让Windows界面回归高效与个性化的开源解决方案 【免费下载链接】Open-Shell-Menu Classic Shell Reborn. 项目地址: https://gitcode.com/gh_mirrors/op/Open-Shell-Menu 当项目经理王工在Windows 11电脑上第5次点击"所有应用"按钮…...
别再乱选ASCII/HEX了!野火串口调试助手发送接收区配置详解(附实战案例)
串口通信调试实战:ASCII与HEX模式的选择艺术 调试智能家居设备时,你是否遇到过发送"ON"指令毫无反应,接收区却显示一堆乱码的尴尬?这往往不是设备故障,而是串口调试中最常见的模式选择错误。作为嵌入式开发者…...
OmenSuperHub终极指南:简单三步掌控暗影精灵硬件性能
OmenSuperHub终极指南:简单三步掌控暗影精灵硬件性能 【免费下载链接】OmenSuperHub 项目地址: https://gitcode.com/gh_mirrors/om/OmenSuperHub 你是否厌倦了官方Omen Gaming Hub的臃肿体积和烦人广告?是否希望获得纯净的硬件控制体验…...
第一次降AIGC率不知道从哪入手?这份保姆级操作手册帮你
第一次操作的话,照着下面的步骤来,15分钟内搞定降AIGC率、降AI工具保姆级测评2026、降AI。 工具选嘎嘎降AI(www.aigcleaner.com),达标率99.26%,有退款保障,操作也不复杂。 准备工作 需要准备的…...
一文了解嵌入式硬件通信核心:串口/CAN/以太网,底层逻辑居然全一样!
做嵌入式、工控、硬件通信开发久了,总会有一个突然顿悟的瞬间:串口、以太网、CAN、TCP、USB、蓝牙、Modbus……这些看似毫无关联、应用场景天差地别的通信方式,扒开底层逻辑才发现,居然是同一个模子刻出来的。看透这一点后&#x…...
Excel也能搞定GRR!不用买昂贵软件,这份保姆级模板和计算指南请收好
Excel也能搞定GRR!不用买昂贵软件,这份保姆级模板和计算指南请收好 在制造业质量管理中,测量系统分析(MSA)是确保数据可靠性的基石。但现实情况是,许多中小企业和初创团队面对动辄上万元的专业统计软件只能…...
从零构建STM32 OTA升级系统:BootLoader设计、IAP实现与APP无缝跳转实战
1. 为什么需要OTA升级系统 想象一下你开发的智能硬件产品已经卖出去几千台,突然发现固件有个致命bug需要修复,或者要增加一个用户期待已久的新功能。传统做法是让用户把设备寄回工厂,或者带着设备到维修点刷机——这简直是开发者的噩梦&#…...
通信确定性可视化冗余现场总线技术开发白皮书(能源化工交通高可靠行业 Profibus DP CAN PROFINET EtherNet/IP SPE APL)
1.前言现场总线是工业物联网的核心支撑技术,但当前国际主流方案在国内应用中普遍存在开发门槛高、硬件成本高、调试维护复杂、冗余配置昂贵等问题,难以满足中小型自动化项目及国产控制系统对高性价比、高可靠性通信的需求。CANWeb现场总线深度融合CAN的高…...
