(二分查找)leetcode1539. 第 k 个缺失的正整数

news/2024/3/29 23:58:42/文章来源:https://blog.csdn.net/qq_44842918/article/details/129275521

文章目录

  • 一、题目
    • 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;}
}

三、本题小知识

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_75677.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SQLite安装及常用语句

SQLite简介SQLite 是一个软件库&#xff0c;实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是在世界上最广泛部署的 SQL 数据库引擎。SQLite 源代码不受版权限制。SQLite安装官网下载 SQLite Download Page新建一个sqlite文件夹&#xff0c;将下载…

【Servlet篇2】创建一个web项目

在上一篇文章当中&#xff0c;已经提到了什么是Maven&#xff0c;以及如何使用maven从中央仓库下载jar包。【Tomcat与Servlet篇1】认识Tomcat与Maven_革凡成圣211的博客-CSDN博客Tomcat&#xff0c;mavenhttps://blog.csdn.net/weixin_56738054/article/details/129228140?spm…

2023年java春招面试题及答案

2023年java春招面试题1、下面有关jdbc statement的说法错误的是&#xff1f;2、下面有关JVM内存&#xff0c;说法错误的是&#xff1f;3、下面有关servlet service描述错误的是&#xff1f;4、下面有关servlet和cgi的描述&#xff0c;说法错误的是&#xff1f;5、下面有关SPRIN…

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

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

开发场景中前端交付的对于后端数据的获取功能书写+页面简繁体转换+页面链接跳转新页面

1&#xff0c;开发场景中前端交付对于后端数据的获取功能书写 首先&#xff0c;我们明确基本逻辑概念&#xff0c;前端获取数据本质是利用ajax中的api接口来获取变量&#xff0c;再将其导入我们的data&#xff1b; 明确基本概念开发就可以进行ajax的定义 下文中e变量是获取前端…

全志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设计…

【观察】连续八年霸榜云数据库“领导者”,揭秘亚马逊云科技背后的“统治力”...

日前&#xff0c;全球市场分析机构 Gartner发布《2022 云数据库管理系统魔力象限》报告。其中&#xff0c;在Gartner本次魔力象限报告评估的20家供应商中&#xff0c;亚马逊云科技在纵轴“执行能力”和横轴“愿景完整性”两个维度分别处于最高、最右位置&#xff0c;这也是亚马…

ANTLR的IDE——ANTLRWorks2的安装及基本使用

1. ANTLRWorks2的简单介绍 ① ANTLR官网对ANTLRWorks2的介绍 ANTLRWorks 2.此IDE是ANTLR v3 / v4语法以及StringTemplate模板的复杂编辑器。 它可以运行ANTLR工具来生成识别器&#xff0c;并可以运行TestRig&#xff08;在命令行上运行&#xff09;来测试语法。 要将ANTLR生成…

Java内置队列和高性能队列Disruptor

一、队列简介 队列是一种特殊的线性表&#xff0c;遵循先入先出、后入后出&#xff08;FIFO&#xff09;的基本原则&#xff0c;一般来说&#xff0c;它只允许在表的前端进行删除操作&#xff0c;而在表的后端进行插入操作&#xff0c;但是java的某些队列运行在任何地方插入删…

EEGLAB处理运动想象脑电数据

最近在看论文时&#xff0c;经常看到作者处理数据的过程&#xff0c;之前都是一代而过&#xff0c;知道怎么处理就可以了&#xff0c;一直没有实践&#xff0c;最近需要一些特殊的数据&#xff0c;需要自己处理出来&#xff0c;这里尝试着自己用MATLAB处理数据&#xff0c;记录…

Kubernetes12:k8s集群安全机制 ***与证书生成***

Kubernetes12&#xff1a;k8s集群安全机制 1、概述 1&#xff09;访问一个k8s集群的时候&#xff0c;需要经过以下三个步骤才能完成具体操作 第一步&#xff1a;认证操作第二部&#xff1a;鉴权操作&#xff08;授权&#xff09;第三部&#xff1a;准入控制操作 2&#xff…

Java枚举详解

一.枚举 1.为什么有枚举&#xff1f; 如果我们的程序需要表示固定的几个值&#xff1a; 比如季节&#xff1a;spring (春)&#xff0c;summer(夏)&#xff0c;autumn(秋)&#xff0c;winter(冬) 用常量表示&#xff1a; public static final int SEASON_SPRING 1;public st…

记一次MySQL数据迁移到SQLServer全过程

为什么要做迁移&#xff1f; 由于系统版本、数据库的升级&#xff0c;导致测试流程阻塞&#xff0c;为了保证数据及系统版本的一致性&#xff0c;我又迫切需要想用这套环境做性能测试&#xff0c;所以和领导、开发请示&#xff0c;得到批准后&#xff0c;便有了这次学习的机会…

idea 安装JUnit单元测试框架

JUnit是一套专门用于java的单元测试框架&#xff0c;主要是测试方法 junit4官方网站&#xff1a; JUnit – About junit5官方网站&#xff1a;JUnit 5 框架依赖&#xff1a;junit-4.12.jar&#xff1b;hamcrest-core-1.3.jar 安装步骤&#xff1a; &#xff08;1&#xff…

hiveSQL开窗函数详解

hive开窗函数 文章目录hive开窗函数1. 开窗函数概述1.1 窗口函数分类1.2 窗口函数和普通聚合函数的区别2. 窗口函数的基本用法2.1 基本用法2.2 设置窗口的方法2.2.1 window_name2.2.2 partition by2.2.3 order by 子句2.2.4 rows指定窗口大小窗口框架2.3 开窗函数中加 order by…

一文吃透 Spring 中的 AOP 编程

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

【C++】二叉搜索树的模拟实现

一、概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根节点的值它的左右子树也分别…

开源ZYNQ AD9361软件无线电平台

&#xff08;1&#xff09; XC7Z020-CLG400 &#xff08;2&#xff09; AD9363 &#xff08;3&#xff09; 单发单收&#xff0c;工作频率400MHz-2.7GHz &#xff08;4&#xff09; 发射带PA&#xff0c;最大输出功率约20dbm &#xff08;5&#xff09; 接收带LNA&#xff0c;低…

Linux学习(9.1)文件系统的简单操作

以下内容转载自鸟哥的Linux私房菜 原文&#xff1a;鸟哥的 Linux 私房菜 -- Linux 磁盘与文件系统管理 (vbird.org) 磁盘与目录的容量 df&#xff1a;列出文件系统的整体磁盘使用量&#xff1b;du&#xff1a;评估文件系统的磁盘使用量(常用在推估目录所占容量) df du 实体…

微信小程序 《新闻列表》 案例

目录&#xff1a;一&#xff0c;步骤。要求1&#xff1a;主页头部的轮播图要求2&#xff1a;中间内容上的信息案列排版。要求3&#xff1a;上拉加载内容。要求4&#xff1a;在信息加载完成后&#xff0c;给用户提示二&#xff0c;过程中要注意的几点。1.在微信小程序中&#xf…