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

算法小抄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&#xff0c;JRE&#xff0c;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 浮点表示规格化和非规格化舍入浮点运算现代计算机存储和处理的信息以二值信号表示&#xff0c;这些二进制数字称为位&#xff0c;为什么要用二进制来进行编码&#xff1f;因为二进制只有1和0两种…...

Chapter2.2:线性表的顺序表示

该系列属于计算机基础系列中的《数据结构基础》子系列&#xff0c;参考书《数据结构考研复习指导》(王道论坛 组编)&#xff0c;完整内容请阅读原书。 2.线性表的顺序表示 2.1 顺序表的定义 线性表的顺序存储亦称为顺序表&#xff0c;是用一组地址连续的存储单元依次存储线性表…...

老马闲评数字化「4」做数字化会不会被供应商拿捏住

原文作者&#xff1a;行云创新CEO 马洪喜 导语 开年过后业务特别的繁忙&#xff0c;出差也比较多&#xff0c;所以有段时间没更新了&#xff0c;对不住大家&#xff01; 上一集&#xff08;您可以查看“行云创新”主页阅读原文&#xff09;咱们聊了数字化转型的“想转、急转、…...

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析取范式&#xff08;基本积之和&#xff09;&#xff0c;合取范式&#xff08;基本和之积&#xff09;1.3.6合式公式1…...

软件测试分类知识分享,第三方软件测试机构收费贵不贵?

软件测试可以很好的检验软件产品的质量以及规避产品上线之后可能会发生的错误&#xff0c;随着技术的发展&#xff0c;软件测试已经是一个完整且体系庞大的测试活动&#xff0c;不同的测试领域有着不同的测试方法、技术与名称&#xff0c;那么具体有哪些分类呢? 一、软件测试…...

爬虫(二)解析数据

文章目录1. Xpath2. jsonpath3. BeautifulSoup4. 正则表达式4.1 特殊符号4.2 特殊字符4.3 限定符4.3 常用函数4.4 匹配策略4.5 常用正则爬虫将数据爬取到后&#xff0c;并不是全部的数据都能用&#xff0c;我们只需要截取里面的一些数据来用&#xff0c;这也就是解析爬取到的信…...

【C++、C++11】可变参数模板、lambda表达式、包装器

文章目录&#x1f4d6; 前言1. 可变参数模板1.1 万能模板&#xff1a;1.2 完美转发&#xff1a;1.3 可变参数模板的使用&#xff1a;1.4 emplace_back&#xff1a;2. lambda表达式2.1 lambda表达式的定义&#xff1a;2.2 lambda表达式的用法&#xff1a;2.2 - 1 捕捉列表的用法…...

外贸主机测评

一、俄罗斯vps 服务商&#xff1a; JUSTG: Home - Sun Network Company Limited LOCVPS: LOCVPS 全球云 - 十年老牌 为跨境外贸/远程办公/网站建设提供澎湃动力 JUSTHOST: justhost.ru RUVDS: Gcorelabs: 二、主机测评指标&#xff1a; 1、速度、延迟、丢包、路由测试…...

Meta CTO:Quest 2生命周期或比预期更久

前不久&#xff0c;Meta未来4年路线图遭曝光&#xff0c;泄露了该公司正在筹备中的一些AR/VR原型。除此之外&#xff0c;还有消息称Quest Pro或因销量不佳&#xff0c;而不再迭代。毫无疑问&#xff0c;Meta的一举一动持续受到行业关注&#xff0c;而面对最近的爆料&#xff0c…...

Vector - CAPL - 文件处理函数

在当前平台化的趋势下,就算是协议层测试依然需要适配各种各样的项目,也需要处理各类型的文件,那我们如何对文件进行读取、写入、修改等类型的操作呢?今天我们就会介绍此类型的函数,主要适用于text、bin文件的处理。 打开文件 Open...

实力加持!RestCloud完成多方国产化适配,携手共建信创生态

近年来&#xff0c;随着数字化建设进入深水区&#xff0c;企事业单位对信息安全重视程度与日俱增&#xff0c;核心技术自主可控已成为时代呼唤&#xff0c;国产化浪潮日益汹涌澎湃。近日&#xff0c;RestCloud在国产化方面取得新进展&#xff0c;完成了全部产品线信创环境的多方…...

Unity 3D GUI教程||OnGUI TextArea 控件||OnGUI ScrollView 控件

OnGUI TextArea 控件 Unity 3D TextArea 控件用于创建一个多行的文本编辑区。用户可以在多行文本编辑区编辑文本内容。 该控件可以对超出控件宽度的文本内容实现换行操作。 TextArea 控件同样会将当前文本编辑区中的文本内容以字符串形式返回。 开发人员可以通过创建 Strin…...

Leetcode.828 统计子串中的唯一字符

题目链接 Leetcode.828 统计子串中的唯一字符 Rating &#xff1a; 2034 题目描述 我们定义了一个函数 countUniqueChars(s)来统计字符串 s中的唯一字符&#xff0c;并返回唯一字符的个数。 例如&#xff1a;s "LEETCODE"&#xff0c;则其中 "L", "…...

Hibernate 相关特性

1. Hibernate一般使用hql进行查询&#xff0c;但也有sql执行的方法 Native sql 查询,。需要注意的是&#xff0c;使用Native SQL查询可能会破坏Hibernate的缓存机制&#xff0c;并可能导致性能问题 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…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...