(二分查找)leetcode1539. 第 k 个缺失的正整数
文章目录
- 一、题目
- 1、题目描述
- 2、基础框架
- 3、原题链接
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 三、本题小知识
一、题目
1、题目描述
给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。
示例 1:
输入:arr = [2,3,4,7,11], k = 5
输出:9
解释:缺失的正整数包括 [1,5,6,8,9,10,12,13,…] 。第 5 个缺失的正整数为 9 。
示例 2:
输入:arr = [1,2,3,4], k = 2
输出:6
解释:缺失的正整数包括 [5,6,7,…] 。第 2 个缺失的正整数为 6 。
2、基础框架
- C++版本给出的基础框架如下:
3、原题链接
https://leetcode.cn/problems/kth-missing-positive-number/
二、解题报告
1、思路分析
(1)(1)(1)arr[i] - i - 1的值代表前面缺失了多少个数。比如示例1中arr[4] - 4 - 1 = 11 - 4 -1 = 6。代表11前面缺失了6个数。
(2)(2)(2)考虑普遍情况,当缺失的数在数组中最大最小元素代表的区间范围内时,我们只要找到arr[i] - i - 1 >= k > arr[i-1] - i -1 -1的位置i,缺失的数肯定位于arr[i-1]和arr[i]之间。
(3)(3)(3)缺失的数为arr[i] - (arr[i] - i - 1 - k + 1) = i+k
(4)(4)(4)对于边界条件,我们提前判断,当arr[0] > k时,说明缺失的第k个数在数组左边外侧,直接返回k。当arr[arr.length-1] < k时,说明缺失的第k个数在数组右边外侧,直接返回k + arr.length
2、时间复杂度
时间复杂度为O(logn)
3、代码详解
class Solution {public int findKthPositive(int[] arr, int k) {if (arr[0] > k) {return k;}if (arr[arr.length - 1] - arr.length < k) {return k + arr.length;}int l = 0;int r = arr.length - 1;while(l < r) {int mid = l + (r - l) / 2;if (arr[mid] - mid - 1 < k) {l = mid + 1;} else {r = mid;}}return r + k;}
}
三、本题小知识
相关文章:
(二分查找)leetcode1539. 第 k 个缺失的正整数
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识一、题目 1、题目描述 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。 请你找到这个数组里第 k 个缺失的正整数。 示例 1: 输入&…...
yaml文件格式详解及实例
🍁博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 文章目录yaml简介yaml语法规则Yaml语法实例数组…...
AOP在PowerJob中的使用,缓存锁保证并发安全,知识细节全总结
这是一篇简简单单的文章,需要你简简单单看一眼就好,如果有不明白的地方,欢迎留言讨论。 在之前的文章中出现过一次AOP的使用,就是在运行任务之前,需要判断一下,触发该任务执行的server,是不是数…...
对账平台设计
背景 随着公司业务的蓬勃发展,交易履约清结算业务的复杂性也在不断的增高,资金以及各种数据的一致性和准确性也变得越发重要。 以交易链路为例,存在着如下一些潜在的不一致场景: 订单支付成功了,但是订单状态却还是“…...
JavaEE进阶第五课:SpringBoot的创建和使用
上篇文章介绍了Bean 作用域和生命周期,这篇文章我们将会介绍SpringBoot的创建和使用 目录1.为什么要学习StringBoot1.1什么是SpringBoot1.2SpringBoot的优点2.如何用Idea创建SpringBoot项目3.项目目录介绍和运行3.1输入Helloworld结尾1.为什么要学习StringBoot 在前…...
我带过的一名C++实习生——Z同学
刚开始带Z同学,吃饭聊天时,我顺便了解了下他的擅长:linux平台下C、C网络编程。 接下来的实习,主要分为两个阶段:小组公共培训和项目实训。 小组公共培训为期2周,主要学习和了解公司文化制度,讲师…...
面试题13. 机器人的运动范围
面试题13. 机器人的运动范围 难度:middle\color{orange}{middle}middle 题目描述 地上有一个 mmm 行 nnn 列的方格,从坐标 [0,0][0,0][0,0] 到坐标 [m−1,n−1][m-1,n-1][m−1,n−1] 。一个机器人从坐标 [0,0][0, 0][0,0] 的格子开始移动,它…...
LeetCode189_189. 轮转数组
LeetCode189_189. 轮转数组 一、描述 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,…...
java Files和Paths的使用详解 附有使用demo
前言 Java Files和Paths是Java 7中引入的新API,用于处理文件和目录。Files类提供了许多有用的静态方法来操作文件和目录,而Path类则表示文件系统中的路径。 创建文件和目录 在Java中创建文件和目录非常简单。我们可以使用Files类的createFile()方法和…...
如何使用ApacheTomcatScanner扫描Apache Tomcat服务器漏洞
关于ApacheTomcatScanner ApacheTomcatScanner是一个功能强大的Python脚本,该脚本主要针对Apache Tomcat服务器安全而设计,可以帮助广大研究人员轻松扫描和检测Apache Tomcat服务器中的安全漏洞。 功能介绍 1、支持使用多线程Worker搜索Apache Tomcat服…...
js中的定时器 setTimeout()和setInterval()
JavaScript 定时器,有时也称为“计时器”,用来在经过指定的时间后执行某些任务,类似于我们生活中的闹钟。 在 JavaScript 中,我们可以利用定时器来延迟执行某些代码,或者以固定的时间间隔重复执行某些代码。例如&…...
【吃透Js】深入学习浅拷贝和深拷贝
一、JavaScript数据类型原始类型对象类型二、原始类型和对象类型的区别1.原始类型2.引用类型3.复制4.比较5.值传递三、浅拷贝概念实现方法四、深拷贝概念五、浅拷贝、深拷贝和赋值的区别浅拷贝和赋值六、小结想要真正搞明白深浅拷贝,你必须要熟练掌握赋值、对象在内…...
AUTOSAR为啥要开发新的社区商业模式?
总目录链接>> AutoSAR入门和实战系列总目录 文章目录1 自适应平台架构中的集群更新1.1 ara::diag 服务(诊断)更新1.2 信号到服务映射和自动驾驶接口让我们讨论一下信号到服务映射服务:Automated Driving Interface:2 车载应用商店概念本文介绍Re…...
数据结构和算法面试常见题必考以及前端面试题
1.数据结构和算法 1.1 反转单向链表 public class Node {public int value;public Node next; }public Node reverseList(Node head) {Node pre null;Node next null;while (head ! null) {next head.next;head.next pre;pre head;head head.next}return pre; }1.2 在顺…...
一文解决Python所有报错
前言 Python是一种强大的编程语言,但是它也有一些报错,这些报错可能会让你感到困惑。本文将介绍如何解决Python中的常见报错。 首先,让我们来看看Python中最常见的报错:SyntaxError。这种报错表明你的代码中有语法错误,…...
LeetCode 1237. Find Positive Integer Solution for a Given Equation【双指针,二分,交互】
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
【C语言】结构体进阶
一、结构体 1. 结构体的声明 (1) 结构的基础知识 结构是一些值的集合,这些值称为成员变量。结构的每个成员可以是不同类型的变量。(2)结构的声明 struct tag {member-list; }variable-list;例如描述一个学生&#x…...
全志T3+FPGA国产核心板——Pango Design Suite的FPGA程序加载固化
本文主要基于紫光同创Pango Design Suite(PDS)开发软件,演示FPGA程序的加载、固化,以及程序编译等方法。适用的开发环境为Windows 7/10 64bit。 测试板卡为全志T3+Logos FPGA核心板,它是一款基于全志科技T3四核ARM Cortex-A7处理器 + 紫光同创Logos PGL25G/PGL50G FPGA设计…...
深度学习之 imgaug (图像增强)学习笔记
深度学习之 imgaug (图像增强)前言1\. 安装和卸载2\. 示例2.1 基本使用2.2 包含常用的变换示例3 Augmenters常用函数3.1 iaa.Sequential()3.2 iaa.someOf()3.3 iaa.OneOf()3.4 iaa.Sometimes()3.5 iaa.WithColorspace()3.6 iaa.WithChannels()3.7 iaa.No…...
mysql字符串等值查询中条件字段值末尾有空格也能查到数据问题
一、事故还原 我们仍然使用学生信息表,但是我们只需要保留两个字段即可: CREATE TABLE student_info (id int(11) NOT NULL AUTO_INCREMENT COMMENT 学号,name varchar(20) CHARACTER SET utf8 DEFAULT NULL COMMENT 姓名, PRIMARY KEY (id) ) ENGINEIn…...
一个关于事件溯源Event Sourcing的小荔枝,Golang实现
最后更新于2023年3月1日 10:23:13 参考的这个文章:https://martinfowler.com/eaaDev/EventSourcing.html 用C sharp实现的,我改写成Golang了 最简单的例子 func main() {eProc : NewEventProcessor()//refact : Cargo{Name: "Refactoring"}…...
Vue3 组合式函数,实现minxins
截至目前,组合式函数应该是在VUE 3应用程序中组织业务逻辑最佳的方法。它让我们可以把一些小块的通用逻辑进行抽离、复用,使我们的代码更易于编写、阅读和维护。 一. 什么是“组合式函数”? 根据官方文档说明,在 Vue 应用的概念中…...
什么是钉钉消息推送?
我是3y,一年CRUD经验用十年的markdown程序员👨🏻💻常年被誉为职业八股文选手 在前阵子我就已经接入了钉钉的群机器人和工作消息推送,一直没写文章同步到给大家。 像这种接入渠道的工作,虽然我没接入过&…...
利用 NVIDIATAO 和 WeightBias 加速AI开发
利用 NVIDIATAO 和 Weight&Bias 加速AI开发 利用图像分类、对象检测、自动语音识别 (ASR) 和其他形式的 AI 可以推动公司和商业部门内部的大规模转型。 然而,从头开始构建人工智能和深度学习模型是一项艰巨的任务。 构建这些模型的一个共同先决条件是拥有大量高…...
token - 令牌
文章目录token - 令牌学前须知:1,base64 防君子不防小人2,SHA-256 安全散列算法的一种(hash)3,HMAC-SHA2564,RSA256 非对称加密2.1 JWT - json-web-token1,三大组成2,jwt…...
应用模型开发指南上新介绍
Module、HAP、Ability、AbilitySta-ge、Context……您是否曾经被这些搞不懂又绕不开的知识点困扰? 现在,全新的《应用程序包基础知识》及《应用模型开发指南》为您答疑解惑! 这里有您关注的概念解析、原理机制阐述,也有丰富的…...
Dbeaver连接Hive数据库操作指导
背景:由于工作需要,当前分析研究的数据基于Hadoop的Hive数据库中,且Hadoop服务端无权限进行操作且使用安全模式,在研究了Dbeaver、Squirrel和Hue三种连接Hive的工具,在无法绕开useKey认证的情况下,只能使用…...
【RabbitMQ笔记09】消息队列RabbitMQ之常见方法的使用
这篇文章,主要介绍消息队列RabbitMQ之常见方法的使用。 目录 一、消息队列常见方法 1.1、连接工厂ConnectionFactory 1.2、连接Connection 1.3、通道Channel 1.4、交换机相关方法 (1)exchangeDeclare()声明交换机 1.5、队列相关方法 …...
Linux字符设备驱动模型之设备号
从上文中可知,在Linux用户空间中,如若需要操作硬件设备,均通过/dev目录下的设备文件节点进行操作,基本上每一种设备都会存在一个或者多个的设备节点。 并且在Linux内核中,其表示字符设备的结构成员也提供了相应的设备号…...
C++多态原理
请看下面的程序,该程序演示了多态类对象存储空间的大小。 #include <iostream> using namespace std; class A {public:int i;virtual void func() {}virtual void func2() {} }; class B : public A {int j;void func() {} }; int main() {cout << si…...
PMP认证与NPDP认证哪个含金量高?
两个证涉及的领域不一样的,一个是项目管理,对应的是项目经理;一个是产品管理,对应的是产品经理。含金量不能相比,但在各自的领域的含金量是很高的,至少专业程度或者知名度是最高的。 我来分别说一下PMP认证…...
改进YOLOv7-Tiny系列:首发改进结合BiFPN结构的特征融合网络,网络融合更多有效特征,高效涨点
💡该教程为改进进阶指南,属于《芒果书》📚系列,包含大量的原创首发改进方式, 所有文章都是全网首发原创改进内容🚀 内容出品:CSDN博客独家更新 @CSDN芒果汁没有芒果 💡本篇文章 基于 YOLOv5、YOLOv7芒果改进YOLO系列:芒果改进YOLOv7-Tiny系列:首发改进结合BiFPN结…...
PPC Insights系列:洞见安全多方图联邦
开放隐私计算开放隐私计算开放隐私计算OpenMPC是国内第一个且影响力最大的隐私计算开放社区。社区秉承开放共享的精神,专注于隐私计算行业的研究与布道。社区致力于隐私计算技术的传播,愿成为中国 “隐私计算最后一公里的服务区”。183篇原创内容公众号知…...
SQLite注入记录(目前最全、核心函数用法、布尔盲注、时间盲注、webshell、动态库,绕过方式)
目录 与Mysql区别 全部核心函数 普通注入 查询所有列 查看所有表名...
Java简单的生成/解析二维码(zxing qrcode)
Hi I’m Shendi Java简单的生成/解析二维码(zxing qrcode) 在之前使用 qrcode.js 方式生成二维码,但在不同设备上难免会有一些兼容问题,于是改为后端(Java)生成二维码图片 这里使用 Google 的 zxing包 Jar…...
若依项目导出后端响应的Excel文件流处理
若依开源项目:http://doc.ruoyi.vip/ruoyi-vue 问题 前端 1. download.js 添加自定义方法 /*** 自定义方法:导出后端响应的 excel 文件流* param url 请求后端的接口地址 例如:"/downloadExcel"* param name 响应后的文件名称&…...
华为OD机试【独家】提供C语言题解 - 数组排序
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明数组…...
JVM详解——内存结构
文章目录内存结构1、 运行时数据区2、虚拟机栈3、本地方法栈4、程序计数器5、 堆6、方法区7、运行时常量池8、内存溢出和内存泄漏9、 堆溢出内存结构 1、 运行时数据区 Java虚拟机在运行Java程序期间将管理的内存划分为不同的数据区,不同的区域负责不同的职能&…...
Jvisualvm监控Tomcat以及相关参数优化
Tomcat阻塞模式 阻塞模式(BIO) 客户端和服务器创建一个连接,它就会创建一个线程来处理这个连接,以为这客户端创建了几个连接,服务端就需要创建几个线程来处理你,导致线程会产生很多,有很多线程…...
界面组件DevExpress WinForms v22.2 - 全面升级数据展示功能
DevExpress WinForms拥有180组件和UI库,能为Windows Forms平台创建具有影响力的业务解决方案。DevExpress WinForms能完美构建流畅、美观且易于使用的应用程序,无论是Office风格的界面,还是分析处理大批量的业务数据,它都能轻松胜…...
正点原子第一期
ZYNQ是一个fpga用来硬件编程,外加一个软件编程 FPGA是可通过编程来修改其逻辑功能的数字集成电路 第三篇语法篇 第七章 verilog HDL语法 Verilog的简介 可编程逻辑电路:允许用户自行修改内部连接的集成电路,其内部的电路结构可以通过编程数…...
「mysql是怎样运行的」第24章 一条记录的多幅面孔---事务的隔离级别与MVCC
「mysql是怎样运行的」第24章 一条记录的多幅面孔—事务的隔离级别与MVCC 文章目录「mysql是怎样运行的」第24章 一条记录的多幅面孔---事务的隔离级别与MVCC一、事前准备二、事务的隔离级别事务并发执行遇到的问题SQL标准中的四种隔离级别MySQL中支持的四种隔离级别三、MVCC原…...
入门Java第十五天 线程
一、多线程 1.1进程和线程 进程:进程就是操作系统中运行的每一个应用程序。例如:微信,QQ 线程:线程是进程中的每一个任务。 多线程:在一个进程中,可以同时执行多个线程。同时完成多个任务。 并发&#x…...
探索用卷积神经网络实现MNIST数据集分类
问题对比单个全连接网络,在卷积神经网络层的加持下,初始时,整个神经网络模型的性能是否会更好。方法模型设计两层卷积神经网络(包含池化层),一层全连接网络。选择 5 x 5 的卷积核,输入通道为 1&…...
MySQL 索引失效场景
1,前言 索引主要是为了提高表的查询速率,但在某些情况下,索引也会失效的情况。 2,失效场景 2.1 最左前缀法则 查询从索引最左列开始,如果跳过索引中的age列,那么age后面字段的索引都将失效,…...
Xcode开发工具,图片放入ios工程
Xcode开发工具,图片放入ios工程,有三种方式: 一:Assets Assets.xcassets 一般是以蓝色的Assets.xcassets的文件夹形式在工程中,以Image Set的形式管理。当一组图片放入的时候同时会生成描述文件Contents.jso…...
操作系统权限提升(十九)之Linux提权-SUID提权
系列文章 操作系统权限提升(十八)之Linux提权-内核提权 SUID提权 SUID介绍 SUID是一种特殊权限,设置了suid的程序文件,在用户执行该程序时,用户的权限是该程序文件属主的权限,例如程序文件的属主是root,那么执行该…...
直播 | StarRocks 实战系列第三期--StarRocks 运维的那些事
2023 年开春, StarRocks 社区重磅推出入门级实战系列直播,手把手带你从 Zero to Hero 成为一个 “StarRocks Pro”!通过实际操作和应用场景的结合,我们将帮你系统性地学习 StarRocks 这个当今最热门的开源 OLAP 数据库。本次&…...
KingabseES执行计划-分区剪枝(partition pruning)
概述 分区修剪(Partition Pruning)是分区表性能的查询优化技术 。在分区修剪中,优化器分析SQL语句中的FROM和WHERE子句,以在构建分区访问列表时消除不需要的分区。此功能使数据库只能在与SQL语句相关的分区上执行操作。 参数 enable_partition_pruning 设…...
Operator-sdk 在 KaiwuDB 容器云中的使用
一、使用背景KaiwuDB Operator 是一个自动运维部署工具,可以在 Kubernetes 环境上部署 KaiwuDB集群,借助 Operator 可实现无缝运行在公有云厂商提供的 Kubernetes 平台上,让 KaiwuDB 成为真正的 Cloud-Native 数据库。使用传统的自动化工具会…...