刷题之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…...

基于单片机的无线红外报警系统
**单片机设计介绍,基于单片机的无线红外报警系统 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的无线红外报警系统是一种结合了单片机控制技术和无线红外传感技术的安防系统。该系统通过无线红外传感器实…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...

2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...

使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...