当前位置: 首页 > 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…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...