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

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

第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素,随后对该元素左右进行遍历,找到起始位置和结束位置,代码如下:

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int size = nums.size();int min = 0;int max = size - 1;while(min <= max){int mid = min + (max - min)/2;if(target < nums[mid]){max = mid - 1;}else if(target > nums[mid]){min = mid + 1;}else{while(nums[min] != target){min++;}while(nums[max] != target){max--;}return {min,max};}}return {-1,-1};}
};

执行虽然通过,但测试用时并不是很理想,在 代码随想录 看到的解法是将题目分为三种情况:

  • 情况一: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}

采用二分法来分别寻找左边界和右边界,最终分情况进行return。代码如下:

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一if (leftBorder == -2 || rightBorder == -2) return {-1, -1};// 情况三if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getRightBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界,nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 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 {left = middle + 1;}}return leftBorder;}
};

将上述代码的两个二分查找函数进行合并:

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getBorder(nums, target, true);int rightBorder = getBorder(nums, target, false);// 情况一if (leftBorder == -2 || rightBorder == -2) return {-1, -1};// 情况三if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getBorder(vector<int>& nums, int target, bool flag) {int left = 0;int right = nums.size() - 1;int border = -2;while (left <= right){int middle = left + (right - left)/2;if(flag) { //flag = true,返回左边界if (nums[middle] >= target) { // 寻找左边界,nums[middle] == target的时候更新rightright = middle - 1;border = right;} else {left = middle + 1;}}else{if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界,nums[middle] == target的时候更新leftleft = middle + 1;border = left;}}}return border;}};

相关文章:

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

第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素&#xff0c;随后对该元素左右进行遍历&#xff0c;找到起始位置和结束位置&#xff0c;代码如下&#xff1a; class Solution { public:vector<int> searchRange(vector<int>& nums, int…...

系统分析师-案例分析-数据库

系统分析师-案例分析-数据库 更多软考资料 https://ruankao.blog.csdn.net/ 文章目录 系统分析师-案例分析-数据库数据库考察知识点规范化函数依赖范式1NF2NF3NF 规范化问题不规范化反规范化设计反规范化设计同步问题 并发控制性能优化完整性约束视图安全分布式数据库特点优点…...

【RabbitMQ】使用SpringAMQP的消息队列(Hello Word)和工作队列(Work Queue)

SpringAMQP SpringAMQP中文文档 Hello Word **案例1&#xff1a;**利用SpringAMQP实现HelloWord中的集成消息队列功能 项目结构&#xff0c;如图&#xff1a; 1.引入AMQP依赖&#xff08;父工程中&#xff09; <!--AMQP依赖&#xff0c;包含RabbitMQ--> <dependen…...

项目集成SkyWalking,基于k8s搭建

一、搭建SkyWalking 官方文档&#xff08;英文&#xff09;&#xff1a;skywalking/docs at master apache/skywalking 中文可以使用&#xff1a;GitHub - SkyAPM/document-cn-translation-of-skywalking: [已过期,请使用官网AI文档] The CN translation version of Apache…...

mysql-差异备份流程

4.差异备份流程 差异备份流程&#xff08;重要) 第一次完整备份 innobackupex /xtrabackup innobackupex --userroot --password123456 /xtrabackup2024-05-23_20-25-05 第一次完整备份 2024-05-23_20-40-55 第二次差异备份 2024-05-23_20-47-37 第三次差异备份再往数据库里面…...

基于动态规划算法的DNA序列比对函数,给出两条序列(v和w)的打分矩阵

一.什么是动态规划算法 1.1总体思想 动态规划算法与分治法类似&#xff0c;基本思想也是将待求解的问题分成若干个子问题 经过分解得到的子问题往往不是互相独立的&#xff0c;有些子问题被重复计算多次 如果能够保存已解决的子问题答案&#xff0c;在需要时再找出来已求得…...

Tailwind CSS快速入门

文章目录 初识安装Tailwindcss试用安装快速书写技巧扩展好处Todo 初识 只需书写 HTML 代码&#xff0c;无需书写 CSS&#xff0c;即可快速构建美观的网站 Tailwind CSS 是一个功能类优先的 CSS 框架&#xff0c;它通过提供大量的原子类&#xff08;utility classes&#xff09;…...

Postman使用技巧

Postman是一款广泛使用的API开发和测试工具&#xff0c;专为简化Web服务API的开发、测试、文档编制和协作过程而设计。它支持各种HTTP请求方法&#xff0c;包括GET、POST、PUT、DELETE等&#xff0c;允许用户轻松地构建和发送请求&#xff0c;以及检查响应。 本文介绍几个提升效…...

sqli-labs靶场

less---11 1.求闭合字符 输入1报错说明存在注入点 存在注入点 2.查库名 使用报错注入查库名 admin” and (select 1 from (select count(*),concat(database(),floor(rand(0)*2))x from information_schema.tables group by x)y)# //floor函数报错 3.查表名 admin and upd…...

基于springboot的大创管理系统

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了大创管理系统的开发全过程。通过分析大创管理系统管理的不足&#xff0c;创建了一个计算机管理大创管理系统的方案。文章介绍了大创管理系统的系统分析部分&…...

常用torch.nn

目录 一、torch.nn和torch.nn.functional二、nn.Linear三、nn.Embedding四、nn.Identity五、Pytorch非线性激活函数六、nn.Conv2d七、nn.Sequential八、nn.ModuleList九、torch.outer torch.cat 一、torch.nn和torch.nn.functional Pytorch中torch.nn和torch.nn.functional的区…...

力扣226.翻转二叉树101.对称二叉树

解决二叉树的问题&#xff0c;经常要习惯从递归角度思考 左子树/右子树是否具备某属性、是否属于什么类型&#xff08;和题目要求的判断当前树是否xxx一样&#xff09;&#xff1b; 对左/右子树进行什么操作&#xff08;和题目要求的对当前树的操作一样&#xff09;。 226.翻转…...

word如何按照原本页面审阅文档

1 视图-阅读视图 2 视图&#xff0c;自己看&#xff0c;懒得打字了哈哈...

前端基础入门三大核心之HTML篇:探索WebAssembly —— 开启网页高性能应用新时代

前端基础入门三大核心之HTML篇&#xff1a;探索WebAssembly —— 开启网页高性能应用新时代 WebAssembly基础概念工作原理概览WebAssembly实战示例基本使用 安全性与性能优化防范漏洞实践实际工作中的使用技巧结语与讨论 随着Web技术的飞速发展&#xff0c;前端开发者面临越来越…...

NDIS小端口驱动(四)

NDIS中断相关 1. 注册和取消注册中断&#xff1a; 微型端口驱动程序调用 NdisMRegisterInterruptEx 来注册中断。 驱动程序分配并初始化 NDIS_MINIPORT_INTERRUPT_CHARACTERISTICS 结构&#xff0c;以指定中断特征和函数入口点&#xff0c;驱动程序将结构传递给 NdisMRegister…...

用户态网络缓冲区设计

基于数组实现的环形缓冲区&#xff1a; 优点 使用固定大小的连续空间做用户态缓冲区&#xff0c;利用了内存访问的局部性&#xff0c;可以提高缓存命中率&#xff0c;提高程序性能&#xff0c;在处理大量数据时&#xff0c;缓存的利用率对性能有着很大的影响 正是基于性能的…...

Linux运维工程师基础面试题整理(三)

Linux运维工程师基础面试题整理(三) 1. 文件inode号有什么用?2. 文件的权限怎么设置与管理?3. 如何SSH免密配置?4. 如何快速部署一个web服务?5. 如何更新Linux系统内核?6. centos中如何配置本地yum源?7.Linux 防火墙如何简单配置?8. 有哪些工具可以批量管理Linux服务器…...

基于单片机与传感器技术的汽车起动线路设计

摘 要&#xff1a;在以发动机为动力源的汽车中&#xff0c;起动系统承担起使发动机由非工作状态进入工作状态的重要作用&#xff0c;属于发动机的附属系统。在传统汽车起动系统的基础上提出将单片机与传感器技术运用到起动控制线路中&#xff0c;通过传感器采集发动机工作状态信…...

C#如何通过反射获取外部dll的函数

在C#中&#xff0c;你可以使用反射&#xff08;Reflection&#xff09;来加载外部的DLL&#xff08;动态链接库&#xff09;并获取其中的函数&#xff08;在C#中通常称为方法&#xff09;。但是&#xff0c;请注意&#xff0c;反射主要用于访问类型信息&#xff0c;并且对于非托…...

从零开始傅里叶变换

从零开始傅里叶变换 1 Overview2 傅里叶级数2.1 基向量2.2 三角函数系表示 f ( t ) f(t) f(t)2.2.1 三角函数系的正交性2.2.2 三角函数系的系数 2.3 复指数函数系表示 f ( t ) f(t) f(t)2.3.1 复指数函数系的系数2.3.2 复指数函数系的正交性 2.4 傅里叶级数总结 3 傅里叶变换…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...