刷题之Leetcode34题(超级详细)
34. 在排序数组中查找元素的第一个和最后一个位置
力扣链接(opens new window)https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
示例 1:
- 输入:nums = [5,7,7,8,8,10], target = 8
- 输出:[3,4]
示例 2:
- 输入:nums = [5,7,7,8,8,10], target = 6
- 输出:[-1,-1]
示例 3:
- 输入:nums = [], target = 0
- 输出:[-1,-1]
思路
这道题目如果基础不是很好,不建议大家看简短的代码,简短的代码隐藏了太多逻辑,结果就是稀里糊涂把题AC了,但是没有想清楚具体细节!
对二分还不了解的兄弟先做这两题:
- 704.二分查找(opens new window)https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
- 35.搜索插入位置(opens new window)https://programmercarl.com/0035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE.html
下面我来把所有情况都讨论一下。
寻找target在数组里的左右边界,有如下三种情况:
- 情况一:target 在数组范围的右边或者左边,例如数组{3, 4, 5},target为2或者数组{3, 4, 5},target为6,此时应该返回{-1, -1}
- 情况二:target 在数组范围中,且数组中不存在target,例如数组{3,6,7},target为5,此时应该返回{-1, -1}
- 情况三:target 在数组范围中,且数组中存在target,例如数组{3,6,7},target为6,此时应该返回{1, 1}
这三种情况都考虑到,说明就想的很清楚了。
接下来,在去寻找左边界,和右边界了。
采用二分法来去寻找左右边界,为了让代码清晰,我分别写两个二分来寻找左边界和右边界。
刚刚接触二分搜索的兄弟不建议上来就想用一个二分来查找左右边界,很容易把自己绕进去,建议扎扎实实的写两个二分分别找左边界和右边界
寻找右边界
先来寻找右边界,至于二分查找,如果看过刷题之Leetcode704题(超级详细)-CSDN博客就会知道,二分查找中什么时候用while (left <= right),有什么时候用while (left < right),其实只要清楚循环不变量,很容易区分两种写法。
那么这里我采用while (left <= right)的写法,区间定义为[left, right],即左闭右闭的区间(如果这里有点看不懂了,强烈建议把刷题之Leetcode704题(超级详细)-CSDN博客这篇文章先看了,704题目做了之后再做这道题目就好很多了)
确定好:计算出来的右边界是不包含target的右边界,左边界同理。
可以写出如下代码
int getRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle]==target) {// 寻找右边界,nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;} else if(nums[middle]>target){ right = middle - 1;}else{left=middle-1;
}}return rightBorder;}
寻找左边界
int getLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] == target) { // 寻找左边界,nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else if(nums[middle]>target){right=middle-1;}else{ left=middle+1;
}}return leftBorder;}
处理三种情况
左右边界计算完之后,看一下主体代码,这里把上面讨论的三种情况,都覆盖了
class Solution {int[] searchRange(int[] nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};// 情况三if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};// 情况二return new int[]{-1, -1};}int getRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle]==target) {// 寻找右边界,nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;} else if(nums[middle]>target){ right = middle - 1;}else{left=middle+1;
}}return rightBorder;}int getLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] == target) { // 寻找左边界,nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else if(nums[middle]>target){right=middle-1;}else{ left=middle+1;
}}return leftBorder;}
这份代码在简洁性很有大的优化空间,例如把寻找左右区间函数合并一起。
但拆开更清晰一些,而且把三种情况以及对应的处理逻辑完整的展现出来了。
总结
初学者建议大家一块一块的去分拆这道题目,正如本题解描述,想清楚三种情况之后,先专注于寻找右区间,然后专注于寻找左区间,左右根据左右区间做最后判断。
不要上来就想如果一起寻找左右区间,搞着搞着就会顾此失彼,绕进去拔不出来了。
相关文章:
刷题之Leetcode34题(超级详细)
34. 在排序数组中查找元素的第一个和最后一个位置 力扣链接(opens new window)https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/ 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始…...
从0到1构建uniapp应用-store状态管理
背景 在 UniApp的开发中,状态管理的目标是确保应用数据的一致性,提升用户体验,并简化开发者的工作流程。通过合理的状态管理,可以有效地处理用户交互、数据同步和界面更新等问题。 此文主要用store来管理用户的登陆信息。 重要…...
Uinx线程详解
目录 一.什么是线程? 并发(Concurrency) 并行(Parallelism) 1.1 线程的概念 1.2 线程的基本函数 1.3 线程的基本使用例子: 二.线程的属性 2.1线程属性使用例子 三.线程互斥 3.1互斥锁 3.2互斥锁常用函…...
线性代数笔记23--马尔可夫矩阵、傅里叶级数
1. 马尔可夫矩阵 例子 A [ . 1 . 001 . 3 . 2 . 099 . 3 . 7 0 . 4 ] A \begin{bmatrix} .1 & .001 & .3\\ .2 & .099 & .3\\ .7 & 0 & .4 \end{bmatrix} A .1.2.7.001.0990.3.3.4 马尔可夫矩阵满足条件 λ 1 为特征值 \lambda1为特征…...
Elasticsearch 压测实践总结
背景 搜索、ES运维场景离不开压力测试。 1.宿主机层面变更:参数调优 & 配置调整 & 硬件升级2.集群层面变更:参数调优3.索引层面变更:mapping调整 当然还有使用层面变更,使用API调优(不属于该文章的讨论范围…...
Spirngboot JWT快速配置和使用
2、JWT 2.1、JWT介绍 JWT是JSON Web Token的缩写,即JSON Web令牌,是一种自包含令牌。 是为了在网络应用环境间传递声明而执行的一种基于JSON的开放标准。 JWT的声明一般被用来在身份提供者和服务提供者间传递被认证的用户身份信息,以便于从…...
【Java SE】继承
🥰🥰🥰来都来了,不妨点个关注叭! 👉博客主页:欢迎各位大佬!👈 文章目录 1. 继承1.1 继承是什么1.2 继承的意义1.3 继承的语法1.4 继承的方式1.5 子类中访问父类成员1.5.1 子类中访问…...
设计模式(19):策略模式
策略模式 策略模式对应与解决某一个问题的一个算法族,允许用户从该算法族中任选一个算法解决某一问题,同时可以方便的更换算法或者增加新的算法。并且由客户端决定调用哪个算法。 本质 分离算法,选择实现; 策略模式角色 上下…...
Linux 命令 top 详解
1 top命令介绍 Linux系统中,Top命令主要用于实时运行系统的监控,包括Linux内核管理的进程或者线程的资源占用情况。这个命令对所有正在运行的进程和系统负荷提供不断更新的概览信息,包括系统负载、CPU利用分布情况、内存使用、每个进程的内容…...
Android安卓开发 - 简单介绍(一)
最近呢需要重构还有维护安卓项目,所以最近会从零开始梳理开发的一些知识点以及开发的内容 前面已经写了安装的教程,idea怎么安装,还有官方的开发工具Android Studio怎么安装 2024最新版Android studio安装入门教程(非常详细&…...
AJAX —— 学习(二)
目录 一、利用 JSON 字符串 返回数据 (一)基础代码 (二)原理及实现 二、nodmon 工具 自动重启服务 (一)用途 (二)下载 (三)使用 三、IE 缓存问题 &a…...
CSC博士联培申请时间线
暂时只记得这么多了,有问题会及时修改。 #mermaid-svg-ZMjY9etaS7StCVuw {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ZMjY9etaS7StCVuw .error-icon{fill:#552222;}#mermaid-svg-ZMjY9etaS7StCVuw .e…...
大数据实验三-HBase编程实践
目录 一.实验内容 二.实验目的 三.实验过程截图及说明 1、安装HBase 2、配置伪分布式模式: 3、使用hbase的shell命令来操作表: 4、使用hbase提供的javaAPI来编程实现类似操作: 5、实验总结及心得体会…...
【Python】Pillow支持的图像文件格式
完全支持格式只读格式只写格式仅标识格式BLPCURPALMBUFRBMPDCXPDFGRIBDDSFITSXV ThumbnailsHDF5DIBFLCMPEGEPSFPXGIFFTEXICNSGBRICOGDIMIMTJPEGIPTC/NAAJPEG 2000MCIDASMSPMICPCXMPOPNGPCDPPMPIXARSGIPSDSPIDERQOITGASUNTIFFWALwebpWMF、EMFXBMXPM 参考文献 图像文件格式 - P…...
算法——最小生成树
Prim算法: 算法步骤: 1.选择一个起始节点作为最小生成树的起点。 2.将该起始节点加入最小生成树集合,并将其标记为已访问。 3.在所有与最小生成树集合相邻的边中,选择权重最小的边和它连接的未访问节点。 4.将该边和节点加入最小…...
OpenHarmony相机和媒体库-如何在ArkTS中调用相机拍照和录像。
介绍 此Demo展示如何在ArkTS中调用相机拍照和录像,以及如何使用媒体库接口进行媒体文件的增、删、改、查操作。 本示例用到了权限管理能力ohos.abilityAccessCtrl 相机模块能力接口ohos.multimedia.camera 图片处理接口ohos.multimedia.image 音视频相关媒体业…...
【EasyExcel】多sheet、追加列
业务-EasyExcel多sheet、追加列 背景 最近接到一个导出Excel的业务,需求就是多sheet,每个sheet导出不同结构,第一个sheet里面能够根据最后一列动态的追加列,追加多少得看运营人员传了多少需求列。原本使用的 pig4cloud 架子&…...
韩顺平 | 零基础快速学Python
环境准备 开发工具:IDLE、Pycharm、Sublime Text、Eric 、文本编辑器(记事本/editplus/notepad) Python特点:既支持面向过程OOP、也支持面向对象编程;具有解释性,不需要编程二进制代码,可以直…...
docker部署DOS游戏
下载镜像 docker pull registry.cn-beijing.aliyuncs.com/wuxingge123/dosgame-web-docker:latestdocker-compose部署 vim docker-compose.yml version: 3 services:dosgame:container_name: dosgameimage: registry.cn-beijing.aliyuncs.com/wuxingge123/dosgame-web-docke…...
基于单片机的无线红外报警系统
**单片机设计介绍,基于单片机的无线红外报警系统 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的无线红外报警系统是一种结合了单片机控制技术和无线红外传感技术的安防系统。该系统通过无线红外传感器实…...
【JAVAEE学习】探究Java中多线程的使用和重点及考点
˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…...
Day81:服务攻防-开发框架安全SpringBootStruts2LaravelThinkPHPCVE复现
目录 PHP-框架安全-Thinkphp&Laravel Laravel CVE-2021-3129 RCE Thinkphp 版本3.X RCE-6.X RCE 版本6.X lang RCE J2EE-框架安全-SpringBoot&Struts2 Struct2 旧漏洞(CVE-2016-0785等) struts2 代码执行 (CVE-2020-17530)s2-061 Str…...
.kat6.l6st6r勒索病毒肆虐,这些应对策略或许能帮到你
引言: 近年来,网络安全问题日益凸显,其中勒索病毒更是成为了公众关注的焦点。其中,.kat6.l6st6r勒索病毒以其独特的传播方式和破坏力,给全球用户带来了极大的困扰。本文将深入探讨.kat6.l6st6r勒索病毒的特点…...
maya移除节点 修改节点
目录 maya移除节点 使用 Maya 用户界面: 使用脚本: maya 修改节点名字 使用 Maya 用户界面: 使用 MEL 脚本: 使用 Python 脚本: 注意事项: maya移除节点 使用 Maya 用户界面: 在“层次…...
嵌入式算法开发系列之卡尔曼滤波算法
卡尔曼滤波算法 文章目录 卡尔曼滤波算法前言一、卡尔曼滤波算法原理二、算法应用三、C语言实现总结 前言 在嵌入式系统中,传感器数据通常受到噪声、误差和不确定性的影响,因此需要一种有效的方法来估计系统的状态。卡尔曼滤波算法是一种基于概率理论的…...
简述对css工程化的理解
一、css工程化解决了哪些问题 1、宏观设计:css如何组织、拆分、设计模块结构 2、编码优化:如何更好地编写css 3、构建:如何处理css,使打包结果最优 4、可维护性:最小化后续的变更成本 二、针对问题,如何解…...
.NET 5种线程安全集合
在.NET中,有许多种线程安全的集合类,下面介绍五种我们常用的线程安全集合以及他们的基本用法。 ConcurrentBag ConcurrentBag 是一个线程安全的无序包。它适用于在多线程环境中频繁添加和移除元素的情况。 ConcurrentBag<int> concurrentBag n…...
计算机信息自查
文章目录 操作系统安装时间硬盘序列号查询上网IPMAC地址 操作系统安装时间 可以使用命令行形式,查询windows系统安装时间: wmic OS get InstallDate首先显示年份,然后是月份,然后是日期,然后是安装的确切时间 或者w…...
配置vite配置文件更改项目端口、使用@别名
一、配置vite配置文件更改项目端口 vite官方文档地址:开发服务器选项 | Vite 官方中文文档 (vitejs.dev) 使用: 二、使用别名 1. 安装 types/node types/node 包允许您在TypeScript项目中使用Node.js的核心模块和API,并提供了对它们的类型…...
【LeetCode热题100】【链表】环形链表
题目链接:141. 环形链表 - 力扣(LeetCode) 判断一个链表有没有环可以用快慢指针的方法,如果没有环,那么最终可以让两个指针中一个为空,如果有环,那么快指针终会与慢指针相遇 class Solution {…...
男子做网站/seo优化网络公司排名
VS2010自定义添加创建者、创建时间等个人信息新建文件模版 地址1:http://www.cr173.com/html/11929_1.html 地址2:http://www.jb51.net/softjc/38451.html VS2010已经成为.NET开发人员的必备工具,相比经典版VS2005,到过渡版vs2008…...
企业网站优化的弊端/合肥seo网站排名
因为总是记不住,还要百度或者试验一下,不如干脆记下来 tran属性:position、rotation、scale transform.SetParent(Transform parent, bool worldPositionStays) worldPositionStays:是否保持原本的tran属性 worldPositionStay…...
做网站需要学习多久/平台推广广告宣传词
如果想要返回HTML文件,则需要安装模板引擎。 EJS是一个JavaScript模板库,用来从JSON数据中生成HTML字符串。Koa2框架中ejs可以把数据库查询的数据渲染到模板上面,实现一个动态网站。 Koa2 中使用ejs模板引擎的用法:1、安装 koa-…...
wordpress做第二个/网站收录一键提交
Unclutter for Mac是一款Mac上实用的文件暂存助手,Unclutter类似于 iOS 上的下拉菜单,当我们拖拽一个文件或链接到菜单栏上时,Unclutter会显示出一个暂存空间,让我们把文件或文字放到其中,Unclutter有剪切板、文件存储…...
wordpress 图片菜单/什么软件可以找客户资源
今天看了七月在线算法课。再一次认识了LCS,现在整理记录: LCS(Longest Common Subsequence)最长公共子序列。 一个序列S任意删除若干个字符得到新序列T,那么T叫做S的子序列。 两个序列X和Y的公共子序列中࿰…...
ipv6域名解析 做网站/品牌推广方案ppt
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/baidu_37181928/article/details/80020702Spring 是什么 Spring 是一个开源框架.Spring 为简化企业级应用开发而生. 使用 Spring 可以使简单的 JavaBean 实现以前只有 EJB 才…...