(二分查找)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…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
