算法小抄5-原地哈希
书接上回,学会了数组中重复数字的解法三,相信接下来的题也难不倒你
找到数组中消失的数字
题目链接

题意
对于一个大小为n的数组,数组中所有的数都在[1,n]内,其中有些数字重复了,由于有些数字重复了,另一些数字就一定会确实,这次需要找到所有缺少的数字并且返回结果
有没有发现,原地哈希的题目条件中总会带有大小为n,然后再限制每个数的范围,在之前的数组题中限制的是[0,n-1]这次的题限制的是[1,n]
例子
对于数组[4,3,2,7,8,2,3,1],我们根据原地哈希的规则将该数组重写排列,将下标与值对应,即值=下标+1,这样重新排列而得出的最终结果应该是[1,2,3,4,3,2,7,8],在下标4和下标5的地方元素缺失,此时会被重复的元素2和3随机填充
思路
步骤一: 遍历数组,定义当前下标为i,若当前值与下标不匹配则进行交换,[4,3,2,7,8,2,3,1]这个数组,首先应该交换4和7(下标为nums[i]-1),因此我们可以写出进行交换的条件if(nums[i]!=nums[nums[i]-1])
步骤二: 可以看到在交换后[4,3,2,7,8,2,3,1]这个数组变为[7,3,2,4,8,2,3,1],是不是发现下标0的位置还需要继续交换?,故我们应该把步骤1的if条件更改为循环条件while
步骤三: 经过我们的操作数组已经被变为原地哈希排序后的数组了,接下来只要再遍历一遍数组,找出值!=下标+1的情况,返回结果即可
伪代码
for(num: nums){while(值不对位){交换位置}
}
res=[]
for(num: nums){if(值不对位){res.append(num) }
}
return res
答案
def findDisappearedNumbers(self, nums):n = len(nums)if n <= 1:return []for i in range(n):while nums[i] != nums[nums[i] - 1]:nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]res = []for i in range(n):if nums[i] != i + 1:res.append(i+1)return res
注意到我上次说的,在交换数字时,如果后者用到了前者会导致前者的值被预先覆盖,交换失败哦,写成 nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]才是正确的
缺失的第一个正数
做到这里,想必羊羊已经是一位老司机了,这是一道困难题,但我相信难不倒你
题目链接

题目大意: 对于一个正正数序列它从1开始一直到无限大,我们的目标就是找出当前数组中缺失的第一个正整数,题目中说,时间复杂度为O(n),说明只能遍历一次,常数级别的额外空间,说明不能使用字典和集合,所以原地哈希是我们唯一的出路了
难点
- 该题的难点在于交换条件,如果我们按照上一题的交换条件进行交换,由于数组中的值不一定在[1,n]中,很有可能造成数组下标越界的情况,因此需要增加判断,在不越界的情况下,才能进行交换
- 结果的返回,与上题不同,这题只需要返回第一个正数,所以我们遇到值不对位的情况,直接返回即可
- 再来考虑这样一个情况,如果数组为[1,2,3],意思是数组原本就满足于原地哈希规则了,此时我们是不是应该返回4呢,所以如果第二个循环语句检查过程中没有返回结果,我们在最后返回n+1即可
代码
这里直接给出代码了哦
分割线--------------------------------------------------------------------------------------------------------------
def firstMissingPositive(self, nums):n = len(nums)for i in range(n):while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] for i in range(n):if nums[i] != i + 1:return i + 1return n + 1
ps: range(n)函数在python中用于生成0到n-1的序列,常用于循环语句中
例如:
- range(5)生成的序列是0,1,2,3,4
- range(1,5)生成的序列是1,2,3,4
- range(1,5,2)生成的序列是1,3,这是因为2指定的是步长,而range在三个参数时,前两个参数代表的是一个左闭右开的区间[1,5)
相关文章:
算法小抄5-原地哈希
书接上回,学会了数组中重复数字的解法三,相信接下来的题也难不倒你 找到数组中消失的数字 题目链接 题意 对于一个大小为n的数组,数组中所有的数都在[1,n]内,其中有些数字重复了,由于有些数字重复了,另一些数字就一定会确实,这次需要找到所有缺少的数字并且返回结果 有没有发…...
java零基础入门(1)
java零基础入门一、JRE和JDK1.1 JRE1.2 JDK1.3 IDK,JRE,JVM三者的包含关系二、CMD2.1 打开CMD2.2 常用CMD命令2.2.1 盘符名称 冒号2.2.2 dir2.2.3 cd 目录2.2.4 cd ..2.2.5 cls2.2.6 exit2.2.7 cd \2.2.8 cd \目录\目录\目录\目录2.3 利用快捷cmd打开 Q…...
java socket实例
/*** 启动项目后就创建Server Socket服务*/PostConstructpublic void runServerSocket() {try {ExecutorService executorService Executors.newFixedThreadPool(10);// 创建线程池ServerSocket serverSocket new ServerSocket(9090);// 在设备上配置的服务端监听端口为9090e…...
计算机中信息的表示和处理 整数和小数的二进制表示
信息的表示和处理整数进制字移位运算无符号数和有符号数加法运算小数定点表示IEEE 浮点表示规格化和非规格化舍入浮点运算现代计算机存储和处理的信息以二值信号表示,这些二进制数字称为位,为什么要用二进制来进行编码?因为二进制只有1和0两种…...
Chapter2.2:线性表的顺序表示
该系列属于计算机基础系列中的《数据结构基础》子系列,参考书《数据结构考研复习指导》(王道论坛 组编),完整内容请阅读原书。 2.线性表的顺序表示 2.1 顺序表的定义 线性表的顺序存储亦称为顺序表,是用一组地址连续的存储单元依次存储线性表…...
老马闲评数字化「4」做数字化会不会被供应商拿捏住
原文作者:行云创新CEO 马洪喜 导语 开年过后业务特别的繁忙,出差也比较多,所以有段时间没更新了,对不住大家! 上一集(您可以查看“行云创新”主页阅读原文)咱们聊了数字化转型的“想转、急转、…...
robosuite添加无碰撞的模型
1 前言 最近在使用robosuite时,需要在仿真环境中可视化物体的目标位置,从而方便观察训练情况,可视化的物体有以下要求: 形状尺寸与操作的物体一样半透明只有visual,不与场景其他物体有碰撞可以在每次step后设置位置,且固定在设定的位置,不受重力影响 2 方法 找了半天,最终确…...
JS学习笔记day03
今日内容 零、 复习昨日 CSS 美化,复用,样式文件和表现文件分离便于维护 选择器 {属性:值;…} 引入css 内联文件内部使用style标签外部文件 <link href"路径" rel"stylesheet" type"text/css"> 选择器 基本 idclass标签名 属性 标签名…...
离散数学笔记_第一章:逻辑和证明(3)
1.3 命题等价式1.3.1 逻辑等价式 1.3.2 条件命题和双条件命题的逻辑等价式 1.3.3 德摩根律 1.3.4 可满足性 可满足的 不可满足的 可满足性问题的解 1.3.5析取范式(基本积之和),合取范式(基本和之积)1.3.6合式公式1…...
软件测试分类知识分享,第三方软件测试机构收费贵不贵?
软件测试可以很好的检验软件产品的质量以及规避产品上线之后可能会发生的错误,随着技术的发展,软件测试已经是一个完整且体系庞大的测试活动,不同的测试领域有着不同的测试方法、技术与名称,那么具体有哪些分类呢? 一、软件测试…...
爬虫(二)解析数据
文章目录1. Xpath2. jsonpath3. BeautifulSoup4. 正则表达式4.1 特殊符号4.2 特殊字符4.3 限定符4.3 常用函数4.4 匹配策略4.5 常用正则爬虫将数据爬取到后,并不是全部的数据都能用,我们只需要截取里面的一些数据来用,这也就是解析爬取到的信…...
【C++、C++11】可变参数模板、lambda表达式、包装器
文章目录📖 前言1. 可变参数模板1.1 万能模板:1.2 完美转发:1.3 可变参数模板的使用:1.4 emplace_back:2. lambda表达式2.1 lambda表达式的定义:2.2 lambda表达式的用法:2.2 - 1 捕捉列表的用法…...
外贸主机测评
一、俄罗斯vps 服务商: JUSTG: Home - Sun Network Company Limited LOCVPS: LOCVPS 全球云 - 十年老牌 为跨境外贸/远程办公/网站建设提供澎湃动力 JUSTHOST: justhost.ru RUVDS: Gcorelabs: 二、主机测评指标: 1、速度、延迟、丢包、路由测试…...
Meta CTO:Quest 2生命周期或比预期更久
前不久,Meta未来4年路线图遭曝光,泄露了该公司正在筹备中的一些AR/VR原型。除此之外,还有消息称Quest Pro或因销量不佳,而不再迭代。毫无疑问,Meta的一举一动持续受到行业关注,而面对最近的爆料,…...
Vector - CAPL - 文件处理函数
在当前平台化的趋势下,就算是协议层测试依然需要适配各种各样的项目,也需要处理各类型的文件,那我们如何对文件进行读取、写入、修改等类型的操作呢?今天我们就会介绍此类型的函数,主要适用于text、bin文件的处理。 打开文件 Open...
实力加持!RestCloud完成多方国产化适配,携手共建信创生态
近年来,随着数字化建设进入深水区,企事业单位对信息安全重视程度与日俱增,核心技术自主可控已成为时代呼唤,国产化浪潮日益汹涌澎湃。近日,RestCloud在国产化方面取得新进展,完成了全部产品线信创环境的多方…...
Unity 3D GUI教程||OnGUI TextArea 控件||OnGUI ScrollView 控件
OnGUI TextArea 控件 Unity 3D TextArea 控件用于创建一个多行的文本编辑区。用户可以在多行文本编辑区编辑文本内容。 该控件可以对超出控件宽度的文本内容实现换行操作。 TextArea 控件同样会将当前文本编辑区中的文本内容以字符串形式返回。 开发人员可以通过创建 Strin…...
Leetcode.828 统计子串中的唯一字符
题目链接 Leetcode.828 统计子串中的唯一字符 Rating : 2034 题目描述 我们定义了一个函数 countUniqueChars(s)来统计字符串 s中的唯一字符,并返回唯一字符的个数。 例如:s "LEETCODE",则其中 "L", "…...
Hibernate 相关特性
1. Hibernate一般使用hql进行查询,但也有sql执行的方法 Native sql 查询,。需要注意的是,使用Native SQL查询可能会破坏Hibernate的缓存机制,并可能导致性能问题 String sql "SELECT * FROM users WHERE age > :age"; Query …...
【研究生学术英语读写教程翻译 中国科学院大学Unit1-Unit8】
Unit1 Descartes Was Wrong 笛卡尔错了:“他人在,故我在” Unit2 Are we ready for the next volcanic catastrophe?我们准备好应对下一次火山灾难了吗? Unit3 Theorists,experimentalists and the bias in popular physics理论家,实验家和大众物理学的偏见 unit4 Magic Nu…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
