当前位置: 首页 > news >正文

在排序数组中查找元素的第一个和最后一个位置(力扣)

一.题目介绍

二.题目解析

使用二分进行查找

2.1处理边界情况

如果数组为空,直接返回 [-1, -1],因为无法找到目标值。

int[] ret = new int[2];
ret[0] = ret[1] = -1;
if (nums.length == 0) return ret;

2.2查找左端点(目标值开始位置)

1.初始化指针:

  • left 指向数组的起始位置(索引 0)。
  • right 指向数组的结束位置(索引 nums.length - 1)。

2.二分查找:

  • 计算中间位置 mid = left + (right - left) / 2 (细节一,不然可能陷入死循环)
  • 如果 nums[mid] < target,说明目标值在右半部分,更新 left = mid + 1。
  • 如果 nums[mid] >= target,说明目标值在左半部分或当前位置就是目标值,更新 right = mid。

 

3.循环退出并判断:

  • 当循环条件是left<right 进行判断,不能是left<=right(细节二,不然可能会陷入死循环)
  • 当 left == right 时,循环结束,此时 left 或 right 指向目标值的第一个位置(如果存在)
  • 如果 nums[right] != target,说明目标值不存在,直接返回 [-1, -1],否则设置ret[ 0 ] = left,保存开始位置。
     

细节一解析:

求中间位置有两种:

mid = left + (right - left) / 2(数组长度是奇数则在中间位置,偶数长度在中间位置偏左)

mid = left + (right - left + 1) / 2(数组长度是奇数则在中间位置,偶数长度在中间位置偏右)

如果使用left + (right - left + 1) / 2可能会陷入死循环

如果剩下两个数字,mid值大于目标值时,需要更新right = mid位置,相当于没移动,循环判断依旧如此,陷入死循环。


细节二解析:

为什么循环判断条件不能是 left <= right?,一张图解释

当left == right时,还要继续进入循环,还是更新right = mid,不移动,如此循环判断,陷入死循环。

视频展示:

在排序数组中查找元素的第一个和最后一个位置(左端点)

 

 2.3查找右端点(目标值结束位置)

 

1.重新初始化指针:

  • left 指向数组的起始位置(索引 0)。
  • right 指向数组的结束位置(索引 nums.length - 1)。

 

2.二分查找:

  • 计算中间位置 mid = left + (right - left + 1) / 2。(细节一,避免陷入死循环)
  • 如果 nums[mid] <= target,说明目标值在右半部分或当前位置就是目标值,更新 left = mid。
  • 如果 nums[mid] > target,说明目标值在左半部分,更新 right = mid - 1。

 

3.循环退出并判断:

  • 当循环条件是left<right 进行判断,不能是left<=right(细节二,不然可能会陷入死循环)
  • 当 left == right 时,循环结束,此时 left 或 right 指向目标值的最后一个位置(如果存在)。
  • 将 ret[1] 设置为 left,即目标值的结束位置。

细节一解析

如果使用left + (right - left ) / 2可能会陷入死循环

如果剩下两个数字,mid值小于等于目标值时,需要更新left= mid位置,相当于没移动,循环判断依旧如此,陷入死循环。


细节二跟求左端点一致。

 视频展示:

在排序数组中查找元素的第一个和最后一个位置(右端点)

 

三.题目源码

class Solution {public int[] searchRange(int[] nums, int target) {//判断边界情况int[]  ret = new int[2];ret[0] = ret [1] = -1;if(nums.length == 0) return ret;//求左端点int left = 0; int right = nums.length - 1;while(left < right){int mid = left + (right - left ) / 2;if(nums[mid] < target) left = mid + 1;else right = mid ;}if(nums[right] != target) return ret;else ret[0] = right;//求右端点left = 0;right = nums.length -1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}ret[1] = left;return ret;}
}

相关文章:

在排序数组中查找元素的第一个和最后一个位置(力扣)

一.题目介绍 二.题目解析 使用二分进行查找 2.1处理边界情况 如果数组为空&#xff0c;直接返回 [-1, -1]&#xff0c;因为无法找到目标值。 int[] ret new int[2]; ret[0] ret[1] -1; if (nums.length 0) return ret; 2.2查找左端点&#xff08;目标值开始位置&#…...

Kafka的消息协议

引言 在学习MQTT消息协议的时候我常常思考kafka的消息协议是什么&#xff0c;怎么保证消息的可靠性和高性能传输的&#xff0c;接下来我们一同探究一下 Kafka 在不同的使用场景和组件交互中用到了多种协议&#xff0c;以下为你详细介绍&#xff1a; 内部通信协议 Kafka 使用…...

Vue 3 30天精进之旅:Day 09 - 组合式API

在Vue 3中&#xff0c;组合式API&#xff08;Composition API&#xff09;是一个引入的新特性&#xff0c;它为开发者提供了一种更灵活的方式来构建和组织组件。与传统的选项API相比&#xff0c;组合式API更注重逻辑的复用和逻辑的组合&#xff0c;让我们更容易处理大型应用中的…...

Day28(补)-【AI思考】-AI会不会考虑自己的需求?

文章目录 AI会不会考虑自己的需求&#xff1f;一、**技术本质&#xff1a;深度≠理解**二、**传播机制&#xff1a;热搜如何制造幻觉**三、**伦理考量&#xff1a;为何必须"撇清"**关键结论 AI会不会考虑自己的需求&#xff1f; 让思想碎片重焕生机的灵魂&#xff1a…...

JavaScript 进阶(下)

原型 what 首先&#xff0c;构造函数通过原型分配的函数是所有对象所 共享的。 然后&#xff0c;JavaScript 规定&#xff0c;每一个构造函数都有一个 prototype 属性&#xff0c;指向另一个对象&#xff0c;所以我们也称为原型对象 这个对象可以挂载函数&#xff0c;对象实…...

selenium自动化测试框架——面试题整理

目录 1. 什么是 Selenium&#xff1f;它的工作原理是什么&#xff1f; 2. Selenium 主要组件 3. 常见 WebDriver 驱动 4. Selenium 如何驱动浏览器&#xff1f; 5. WebDriver 协议是什么&#xff1f; 6. Page Object 模式与 Page Factory 7. 如何判断元素是否可见&#x…...

CF1098F Ж-function

【题意】 给你一个字符串 s s s&#xff0c;每次询问给你 l , r l, r l,r&#xff0c;让你输出 s s s l , r sss_{l,r} sssl,r​中 ∑ i 1 r − l 1 L C P ( s s i , s s 1 ) \sum_{i1}^{r-l1}LCP(ss_i,ss_1) ∑i1r−l1​LCP(ssi​,ss1​)。 【思路】 和前一道题一样&#…...

数据库备份、主从、集群等配置

数据库备份、主从、集群等配置 1 MySQL1.1 docker安装MySQL1.2 主从复制1.2.1 主节点配置1.2.2 从节点配置1.2.3 创建用于主从同步的用户1.2.4 开启主从同步1.2.4 主从同步验证 1.3 主从切换1.3.1 主节点设置只读&#xff08;在192.168.1.151上操作&#xff09;1.3.2 检查主从数…...

电脑要使用cuda需要进行什么配置

在电脑上使用CUDA&#xff08;NVIDIA的并行计算平台和API&#xff09;&#xff0c;需要进行以下配置和准备&#xff1a; 1. 检查NVIDIA显卡支持 确保你的电脑拥有支持CUDA的NVIDIA显卡。 可以在NVIDIA官方CUDA支持显卡列表中查看显卡型号是否支持CUDA。 2. 安装NVIDIA显卡驱动…...

【Unity3D】实现横版2D游戏——攀爬绳索(简易版)

目录 GeneRope.cs 场景绳索生成类 HeroColliderController.cs 控制角色与单向平台是否忽略碰撞 HeroClampController.cs 控制角色攀爬 OnTriggerEnter2D方法 OnTriggerStay2D方法 OnTriggerExit2D方法 Update方法 开始攀爬 结束攀爬 Sensor_HeroKnight.cs 角色触发器…...

JS 时间格式大全(含大量示例)

在 JS 中&#xff0c;处理时间和日期是常见的需求。无论是展示当前时间、格式化日期字符串&#xff0c;还是进行时间计算&#xff0c;JavaScript 都提供了丰富的 API 来满足这些需求。本文将详细介绍如何使用 JavaScript 生成各种时间格式&#xff0c;从基础到高级&#xff0c;…...

opencv裁剪视频区域

import cv2 # 打开视频文件 video_path input.mp4 cap cv2.VideoCapture(video_path) # 获取视频的帧率、宽度和高度 fps int(cap.get(cv2.CAP_PROP_FPS)) width int(cap.get(cv2.CAP_PROP_FRAME_WIDTH)) height int(cap.get(cv2.CAP_PROP_FRAME_HEIGHT)) # 定义裁剪区…...

C++ deque(1)

1.deque介绍 deque的扩容不像vector那样麻烦 直接新开一个buffer 不用重新开空间再把数据全部移过去 deque本质上是一个指针数组和vector<vector>不一样&#xff0c;vector<vector>本质上是一个vector对象数组&#xff01;并且vector<vector>的buffer是不一…...

MapReduce概述

目录 1. MapReduce概述2. MapReduce的功能2.1 数据划分和计算任务调度2.2 数据/代码互定位2.3 系统优化2.4 出错检测和恢复 3. MapReduce处理流程4. MapReduce编程基础参考 1. MapReduce概述 MapReduce是面向大数据并行处理的计算模型、框架和平台:   1. 基于集群的高性能并行…...

DOM操作中childNodes与children的差异及封装方案

引言 在JavaScript的DOM操作中&#xff0c;childNodes和children是开发者常用的属性&#xff0c;但它们在浏览器中的行为差异可能导致兼容性问题。尤其是在处理空白符&#xff08;如换行符\n&#xff09;时&#xff0c;某些浏览器&#xff08;如Chrome和Edge&#xff09;会将空…...

在线课堂小程序设计与实现(LW+源码+讲解)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

分布式系统架构怎么搭建?

分布式系统架构 互联网企业的业务飞速发展&#xff0c;促使系统架构不断变化。总体来说&#xff0c;系统架构大致经历了单体应用架构—垂直应用架构—分布式架构—SOA架构—微服务架构的演变&#xff0c;很多互联网企业的系统架构已经向服务化网格&#xff08;Service Mesh&am…...

大模型知识蒸馏技术(2)——蒸馏技术发展简史

版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl2006年模型压缩研究 知识蒸馏的早期思想可以追溯到2006年,当时Geoffrey Hinton等人在模型压缩领域进行了开创性研究。尽管当时深度学习尚未像今天这样广泛普及,但Hinton的研究已经为知识迁移和模…...

C++初阶 -- 泛型编程(函数模板、类模板)入门

目录 一、泛型编程 1.1 介绍 二、函数模板 2.1 函数模板的概念 2.2 函数模板的格式 2.3 函数模板的原理 2.4 函数模板的实例化 2.4.1 隐式实例化 2.4.2 显式实例化 2.5 模板参数的匹配原则 三、类模板 3.1 类模板的使用格式 3.2 类模板的实例化 一、泛型编程 在有…...

[EAI-027] RDT-1B: a Diffusion Foundation Model for Bimanual Manipulation

Paper Card 论文标题&#xff1a;RDT-1B: a Diffusion Foundation Model for Bimanual Manipulation 论文作者&#xff1a;Songming Liu, Lingxuan Wu, Bangguo Li, Hengkai Tan, Huayu Chen, Zhengyi Wang, Ke Xu, Hang Su, Jun Zhu 论文链接&#xff1a;https://arxiv.org/ab…...

MongoDB常见的运维工具总结介绍

MongoDB 提供了一些强大的运维工具&#xff0c;帮助管理员进行数据库监控、备份、恢复、性能优化等操作。以下是一些常见的 MongoDB 运维工具及其功能介绍&#xff1a; 1. MongoDB Atlas 功能&#xff1a;MongoDB Atlas 是 MongoDB 官方的云托管数据库服务&#xff0c;它提供…...

dify实现原理分析-rag-数据检索的实现

数据检索的总体执行步骤 数据检索总体步骤如下&#xff1a; #mermaid-svg-YCRNdSE7T1d0Etyj {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-YCRNdSE7T1d0Etyj .error-icon{fill:#552222;}#mermaid-svg-YCRNdSE7T1d…...

20个整流电路及仿真实验汇总

0、 前言 以下是关于“20个整流电路及仿真实验汇总”的前言部分: 在现代电力电子技术领域,整流电路作为将交流电(AC)转换为直流电(DC)的关键电路,广泛应用于各类电源设计、信号处理以及电力电子设备中。整流电路不仅能够为电子设备提供稳定的直流电源,还在电力传输、…...

CVE-2020-0796永恒之蓝2.0(漏洞复现)

目录 前言 产生原因 影响范围 漏洞复现 复现环境 复现步骤 防御措施 总结 前言 在网络安全的战场上&#xff0c;漏洞一直是攻防双方关注的焦点。CVE-2020-0796&#xff0c;这个被称为 “永恒之蓝 2.0” 的漏洞&#xff0c;一度引起了广泛的关注与担忧。它究竟是怎样的…...

爬虫基础(一)HTTP协议 :请求与响应

前言 爬虫需要基础知识&#xff0c;HTTP协议只是个开始&#xff0c;除此之外还有很多&#xff0c;我们慢慢来记录。 今天的HTTP协议&#xff0c;会有助于我们更好的了解网络。 一、什么是HTTP协议 &#xff08;1&#xff09;定义 HTTP&#xff08;超文本传输协议&#xff…...

拼车(1094)

1094. 拼车 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a; class Solution { public:bool carPooling(vector<vector<int>>& trips, int capacity) {uint32_t passenger_cnt 0;//将原数据按照from排序auto func_0 [](vector<int> & …...

Ubuntu全面卸载mysql

如果你已经看到whereis mysql输出了与MySQL相关的路径&#xff0c;说明MySQL仍然存在于系统中。要卸载MySQL&#xff0c;可以按照以下步骤操作&#xff0c;确保完全删除所有相关的文件和配置&#xff1a; 1. 停止MySQL服务 首先&#xff0c;停止MySQL服务&#xff1a; sudo …...

@Inject @Qualifier @Named

Inject Qualifier Named 在依赖注入&#xff08;DI&#xff09;中&#xff0c;Inject、Qualifier 和 Named 是用于管理对象创建和绑定的关键注解。以下是它们的用途、依赖配置和代码示例的详细说明&#xff1a; 1. 注解的作用 Inject&#xff1a;标记需要注入的构造函数、字段…...

OpenHarmonyOS 3.2 编译生成的hap和app文件的名称如何配置追加版本号?

找了一圈发现官方的文档都是最新的&#xff0c;3.2很多API都不支持&#xff0c;比如获取OhosAppContext&#xff0c;通过OhosAppContext来获取应用版本号&#xff0c;最终是通过读取app.json5的文件内容来读取版本号&#xff0c;最终修改entry下的hvigorfile.ts如下&#xff0c…...

初始化mysql报错cannot open shared object file: No such file or directory

报错展示 我在初始化msyql的时候报错&#xff1a;mysqld: error while loading shared libraries: libaio.so.1: cannot open shared object file: No such file or directory 解读&#xff1a; libaio包的作用是为了支持同步I/O。对于数据库之类的系统特别重要&#xff0c;因此…...

Vue.js组件开发-实现全屏背景图片滑动切换特效

使用 Vue 实现全屏背景图片滑动切换特效的详细步骤、代码、注释和使用说明。 步骤 创建 Vue 项目&#xff1a;使用 Vue CLI 创建一个新的 Vue 项目。准备图片资源&#xff1a;准备好要用于背景切换的图片&#xff0c;并将它们放在项目的合适目录下。编写 HTML 结构&#xff1…...

AI在自动化测试中的伦理挑战

在软件测试领域&#xff0c;人工智能&#xff08;AI&#xff09;已经不再是遥不可及的未来技术&#xff0c;而是正在深刻影响着测试过程的现实力量。尤其是在自动化测试领域&#xff0c;AI通过加速测试脚本生成、自动化缺陷检测、测试数据生成等功能&#xff0c;极大提升了测试…...

FreeRTOS的任务创建和删除

1&#xff0c;任务创建和删除的API函数 任务的创建和删除本质就是调用FreeRTOS的API函数 动态创建任务&#xff1a; 任务的任务控制块以及任务的栈空间所需的内存&#xff0c;均由 FreeRTOS 从 FreeRTOS 管理的堆中分配。 静态创建任务&#xff1a; 任务的任务控制块以及任务的…...

【C++】STL容器使用与实现详解:vector

文章目录 Ⅰ. vector的介绍和使用一、vector的介绍二、vector的使用 &#xff08;只列出比较重要的&#xff0c;其他的需要时查文档&#xff09;1. vector的定义2. vector iterator&#xff08;迭代器&#xff09;的使用3. vector 容量问题4. vector 增删查改5. 正确释放 vecto…...

【Block总结】动态蛇形卷积,专注于细长和弯曲的局部结构|即插即用

论文信息 标题: Dynamic Snake Convolution based on Topological Geometric Constraints for Tubular Structure Segmentation 作者: 戚耀磊、何宇霆、戚晓明、张媛、杨冠羽 会议: 2023 IEEE/CVF International Conference on Computer Vision (ICCV) 发表时间: 2023年10月…...

物业管理软件引领社区智能化转型提升服务效率与居民生活质量

内容概要 物业管理软件的出现&#xff0c;标志着社区管理方式的一场革命&#xff0c;它不仅仅是一个工具&#xff0c;更是推动智能化转型的关键助力。通过高效的管理功能&#xff0c;物业管理软件在优化服务流程的同时&#xff0c;也提升了居民的生活质量和社区的整体发展活力…...

论文阅读(十三):复杂表型关联的贝叶斯、基于系统的多层次分析:从解释到决策

1.论文链接&#xff1a;Bayesian, Systems-based, Multilevel Analysis of Associations for Complex Phenotypes: from Interpretation to Decision 摘要&#xff1a; 遗传关联研究&#xff08;GAS&#xff09;报告的结果相对稀缺&#xff0c;促使许多研究方向。尽管关联概念…...

线性调整器——耗能型调整器

线性调整器又称线性电压调节器&#xff0c;以下是关于它的介绍&#xff1a; 基本工作原理 线性调整器的基本电路如图1.1(a)所示,晶体管Q1(工作于线性状态,或非开关状态)构成一个连接直流源V和输出端V。的可调电气电阻,直流源V由60Hz隔离变压器&#xff08;电气隔离和整流&#…...

梯度提升用于高效的分类与回归

使用 决策树&#xff08;Decision Tree&#xff09; 实现 梯度提升&#xff08;Gradient Boosting&#xff09; 主要是模拟 GBDT&#xff08;Gradient Boosting Decision Trees&#xff09; 的原理&#xff0c;即&#xff1a; 第一棵树拟合原始数据计算残差&#xff08;负梯度…...

使用Ollama和Open WebUI快速玩转大模型:简单快捷的尝试各种llm大模型,比如DeepSeek r1

Ollama本身就是非常优秀的大模型管理和推理组件&#xff0c;再使用Open WebUI更加如虎添翼&#xff01; Ollama快速使用指南 安装Ollama Windows下安装 下载Windows版Ollama软件&#xff1a;Release v0.5.7 ollama/ollama GitHub 下载ollama-windows-amd64.zip这个文件即可…...

2025年1月个人工作生活总结

本文为 2025年1月工作生活总结。 研发编码 使用sqlite3命令行查询表数据 可以直接使用sqlite3查询数据表&#xff0c;不需进入命令行模式。示例如下&#xff1a; sqlite3 database_name.db "SELECT * FROM table_name;"linux shell使用read超时一例 先前有个编译…...

Windows环境安装nvm,并使用nvm管理nodejs版本教程

目录 1.nvm安装步骤 2.验证nvm是否安装成功 3.查看本地可以安装的所有版本 4.安装特定nodejs版本 5.配置nvm镜像 6.使用特定nodejs版本 7.给nodejs配置镜像和环境变量 8.查看本地安装的所有版本(* 表示当前版本) 9.卸载指定版本的nodejs 前端开发中&#xff0c;不…...

C++中常用的排序方法之——冒泡排序

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【14后&#x1f60a;///计算机爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于C中常用的排序方法之——冒泡排序的…...

SQL进阶实战技巧:如何分析浏览到下单各步骤转化率及流失用户数?

目录 0 问题描述 1 数据准备 2 问题分析 3 问题拓展 3.1 跳出率计算 3.2 计算从浏览商品到支付订单的不同路径的用户数&#xff0c;并按照用户数降序排列。 往期精彩 0 问题描述 统计从浏览商品到最终下单的各个步骤的用户数和流失用户数,并计算转化率 用户表结构和…...

NLP模型大对比:Transformer >Seq2Seq > LSTM > RNN > n-gram

结论 Transformer 大于 传统的Seq2Seq 大于 LSTM 大于 RNN 大于 传统的n-gram n-gram VS Transformer 我们可以用一个 图书馆查询 的类比来解释它们的差异&#xff1a; 一、核心差异对比 维度n-gram 模型Transformer工作方式固定窗口的"近视观察员"全局关联的&q…...

接口技术-第5次作业

目录 作业内容 解答 一、填空题 二、综合题 1.采用AD570通过82C55A与CPU接口&#xff0c;82C55A的端口地址为300H~303H,完成用查询方式采集250个数据&#xff0c;送到2000H开始的存储单元存储。绘制电路连接图&#xff08;AD570的4种主要信号线都要标出&#xff09;。 2…...

实战技巧:如何快速提高网站的收录比例?

本文转自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/28.html 快速提高网站的收录比例是网站优化中的重要目标之一。以下是一些实战技巧&#xff0c;可以帮助你实现这一目标&#xff1a; 一、内容优化 高质量原创内容&#xff1a; 确保网站内…...

WEB集群6-10天

第六天 nginx编译安装 全新的进行编译安装 [rootweb-1 ~]# mkdir /nginx [rootweb-1 ~]# cd /nginx/ [rootweb-1 nginx]# ls [rootweb-1 nginx]#curl -O https://nginx.org/download/nginx-1.26.1.tar.gz解压源码包 [rootweb-1 nginx]#tar xf nginx-1.26.1.tar.gz [rootw…...

10.共享内存 信号量集 消息队列

10.共享内存 信号量集 消息队列 **1. IPC对象操作通用框架****2. 共享内存&#xff08;Shared Memory&#xff09;****3. 信号量集&#xff08;Semaphore&#xff09;****4. 消息队列&#xff08;Message Queue&#xff09;****5. 练习与作业****6. 总结** 1. IPC对象操作通用框…...

玩转大语言模型——使用langchain和Ollama本地部署大语言模型

系列文章目录 玩转大语言模型——使用langchain和Ollama本地部署大语言模型 玩转大语言模型——ollama导入huggingface下载的模型 玩转大语言模型——langchain调用ollama视觉多模态语言模型 玩转大语言模型——使用GraphRAGOllama构建知识图谱 玩转大语言模型——完美解决Gra…...