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

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...