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

(二分查找)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&#xff1a; 输入&…...

yaml文件格式详解及实例

&#x1f341;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; 文章目录yaml简介yaml语法规则Yaml语法实例数组…...

AOP在PowerJob中的使用,缓存锁保证并发安全,知识细节全总结

这是一篇简简单单的文章&#xff0c;需要你简简单单看一眼就好&#xff0c;如果有不明白的地方&#xff0c;欢迎留言讨论。 在之前的文章中出现过一次AOP的使用&#xff0c;就是在运行任务之前&#xff0c;需要判断一下&#xff0c;触发该任务执行的server&#xff0c;是不是数…...

对账平台设计

背景 随着公司业务的蓬勃发展&#xff0c;交易履约清结算业务的复杂性也在不断的增高&#xff0c;资金以及各种数据的一致性和准确性也变得越发重要。 以交易链路为例&#xff0c;存在着如下一些潜在的不一致场景&#xff1a; 订单支付成功了&#xff0c;但是订单状态却还是“…...

JavaEE进阶第五课:SpringBoot的创建和使用

上篇文章介绍了Bean 作用域和生命周期&#xff0c;这篇文章我们将会介绍SpringBoot的创建和使用 目录1.为什么要学习StringBoot1.1什么是SpringBoot1.2SpringBoot的优点2.如何用Idea创建SpringBoot项目3.项目目录介绍和运行3.1输入Helloworld结尾1.为什么要学习StringBoot 在前…...

我带过的一名C++实习生——Z同学

刚开始带Z同学&#xff0c;吃饭聊天时&#xff0c;我顺便了解了下他的擅长&#xff1a;linux平台下C、C网络编程。 接下来的实习&#xff0c;主要分为两个阶段&#xff1a;小组公共培训和项目实训。 小组公共培训为期2周&#xff0c;主要学习和了解公司文化制度&#xff0c;讲师…...

面试题13. 机器人的运动范围

面试题13. 机器人的运动范围 难度&#xff1a;middle\color{orange}{middle}middle 题目描述 地上有一个 mmm 行 nnn 列的方格&#xff0c;从坐标 [0,0][0,0][0,0] 到坐标 [m−1,n−1][m-1,n-1][m−1,n−1] 。一个机器人从坐标 [0,0][0, 0][0,0] 的格子开始移动&#xff0c;它…...

LeetCode189_189. 轮转数组

LeetCode189_189. 轮转数组 一、描述 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 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&#xff0c;用于处理文件和目录。Files类提供了许多有用的静态方法来操作文件和目录&#xff0c;而Path类则表示文件系统中的路径。 创建文件和目录 在Java中创建文件和目录非常简单。我们可以使用Files类的createFile()方法和…...

如何使用ApacheTomcatScanner扫描Apache Tomcat服务器漏洞

关于ApacheTomcatScanner ApacheTomcatScanner是一个功能强大的Python脚本&#xff0c;该脚本主要针对Apache Tomcat服务器安全而设计&#xff0c;可以帮助广大研究人员轻松扫描和检测Apache Tomcat服务器中的安全漏洞。 功能介绍 1、支持使用多线程Worker搜索Apache Tomcat服…...

js中的定时器 setTimeout()和setInterval()

JavaScript 定时器&#xff0c;有时也称为“计时器”&#xff0c;用来在经过指定的时间后执行某些任务&#xff0c;类似于我们生活中的闹钟。 在 JavaScript 中&#xff0c;我们可以利用定时器来延迟执行某些代码&#xff0c;或者以固定的时间间隔重复执行某些代码。例如&…...

【吃透Js】深入学习浅拷贝和深拷贝

一、JavaScript数据类型原始类型对象类型二、原始类型和对象类型的区别1.原始类型2.引用类型3.复制4.比较5.值传递三、浅拷贝概念实现方法四、深拷贝概念五、浅拷贝、深拷贝和赋值的区别浅拷贝和赋值六、小结想要真正搞明白深浅拷贝&#xff0c;你必须要熟练掌握赋值、对象在内…...

AUTOSAR为啥要开发新的社区商业模式?

总目录链接>> AutoSAR入门和实战系列总目录 文章目录1 自适应平台架构中的集群更新1.1 ara::diag 服务&#xff08;诊断&#xff09;更新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是一种强大的编程语言&#xff0c;但是它也有一些报错&#xff0c;这些报错可能会让你感到困惑。本文将介绍如何解决Python中的常见报错。 首先&#xff0c;让我们来看看Python中最常见的报错&#xff1a;SyntaxError。这种报错表明你的代码中有语法错误&#xff0c…...

LeetCode 1237. Find Positive Integer Solution for a Given Equation【双指针,二分,交互】

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

【C语言】结构体进阶

一、结构体 1. 结构体的声明 &#xff08;1&#xff09; 结构的基础知识 结构是一些值的集合&#xff0c;这些值称为成员变量。结构的每个成员可以是不同类型的变量。&#xff08;2&#xff09;结构的声明 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 &#xff08;图像增强&#xff09;前言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字符串等值查询中条件字段值末尾有空格也能查到数据问题

一、事故还原 我们仍然使用学生信息表&#xff0c;但是我们只需要保留两个字段即可&#xff1a; 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…...

Docker部署RabbitMQ后,你的admin账号真的能连上吗?一个权限配置的深度踩坑实录

Docker部署RabbitMQ后admin账号连接失败的深度排查指南 当你用Docker快速部署了RabbitMQ&#xff0c;创建了admin用户&#xff0c;甚至能通过Web界面登录&#xff0c;却在代码中遭遇ACCESS_REFUSED错误时&#xff0c;那种挫败感我深有体会。这不是简单的密码错误问题&#xff0…...

5分钟完全指南:roop-unleashed AI换脸神器从入门到精通

5分钟完全指南&#xff1a;roop-unleashed AI换脸神器从入门到精通 【免费下载链接】roop-unleashed Evolved Fork of roop with Web Server and lots of additions 项目地址: https://gitcode.com/gh_mirrors/ro/roop-unleashed 想要在几分钟内制作专业级的AI换脸视频吗…...

从零部署OpenClaw AI助手:多平台集成与私有化部署实战

1. 项目概述&#xff1a;从零部署你的专属AI助手 最近在折腾AI Agent&#xff0c;发现了一个挺有意思的开源项目叫OpenClaw。简单来说&#xff0c;它就像一个“万能接线员”&#xff0c;能把你的AI大模型&#xff08;比如GPT、Claude、GLM这些&#xff09;的能力&#xff0c;接…...

2025年英雄联盟国服内存级换肤技术深度解析:R3nzSkin架构设计与实现

2025年英雄联盟国服内存级换肤技术深度解析&#xff1a;R3nzSkin架构设计与实现 【免费下载链接】R3nzSkin-For-China-Server Skin changer for League of Legends (LOL) 项目地址: https://gitcode.com/gh_mirrors/r3/R3nzSkin-For-China-Server 你是否曾想过&#xff…...

LT8650S双通道同步降压稳压器设计与汽车电子应用

1. LT8650S双通道同步降压稳压器设计解析在汽车电子和工业设备领域&#xff0c;电源管理系统的设计往往面临严苛挑战。LT8650S作为一款42V输入、双通道4A输出的同步降压稳压器&#xff0c;其Silent Switcher 2架构和6.2μA超低静态电流特性&#xff0c;为工程师提供了高性价比的…...

Android MediaProjection实战:从权限适配到异常处理,构建Android Q+的稳定截屏录屏功能

1. 理解MediaProjection的核心机制 在Android Q及以上版本中&#xff0c;MediaProjection API是系统级截屏和录屏功能的唯一官方入口。与早期版本直接调用adb screencap或反射获取Surface不同&#xff0c;这套机制通过用户显式授权的方式实现隐私保护。我曾在多个项目中遇到过因…...

U-Boot分析【学习笔记】(2)

3. U-Boot 编译 在上篇文章U-Boot分析 【学习笔记】(2)中&#xff0c;给出了基于imx6ull裁剪后的U-Boot源码结构图&#xff0c;但这并不意味着把其他文件进行删除&#xff0c;而是通过配置&#xff08;.config&#xff09;的方式使编译时只选取所需要的文件进行操作。 保持源…...

网页布局基石----盒子模型

目录 一&#xff1a;盒模型的构成 二&#xff1a;盒模型的核心属性 三&#xff1a;标准盒子模型代码实例 CSS控制网页样式是通过盒子模型去实现的&#xff0c;日常中我们所看到的网页上所以标签都可以视为一个盒子。所以网页都是放在盒子里面的。因此&#xff0c;我们首先要…...

告别手动配置!用Tcl脚本一键生成RFSoC RF-ADC/DAC IP核(Vivado 2023.2)

告别手动配置&#xff01;用Tcl脚本一键生成RFSoC RF-ADC/DAC IP核&#xff08;Vivado 2023.2&#xff09; 在FPGA开发中&#xff0c;RFSoC平台的RF数据转换器配置往往是项目迭代中最耗时的环节之一。每次新建工程或调整参数时&#xff0c;开发者都需要在Vivado GUI中重复点击数…...

ARM RAS架构:错误记录与注入机制详解

1. ARM RAS架构概述在现代计算系统中&#xff0c;可靠性、可用性和可服务性(Reliability, Availability, and Serviceability, RAS)已成为关键设计指标。ARM架构通过一系列硬件机制实现这些特性&#xff0c;其中错误记录与注入机制是核心组成部分。这套机制允许系统检测、记录硬…...