在排序数组中查找元素的一个位置和最后一个位置-力扣
第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素,随后对该元素左右进行遍历,找到起始位置和结束位置,代码如下:
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;}};
相关文章:
在排序数组中查找元素的一个位置和最后一个位置-力扣
第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素,随后对该元素左右进行遍历,找到起始位置和结束位置,代码如下: 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:**利用SpringAMQP实现HelloWord中的集成消息队列功能 项目结构,如图: 1.引入AMQP依赖(父工程中) <!--AMQP依赖,包含RabbitMQ--> <dependen…...

项目集成SkyWalking,基于k8s搭建
一、搭建SkyWalking 官方文档(英文):skywalking/docs at master apache/skywalking 中文可以使用:GitHub - SkyAPM/document-cn-translation-of-skywalking: [已过期,请使用官网AI文档] The CN translation version of Apache…...
mysql-差异备份流程
4.差异备份流程 差异备份流程(重要) 第一次完整备份 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总体思想 动态规划算法与分治法类似,基本思想也是将待求解的问题分成若干个子问题 经过分解得到的子问题往往不是互相独立的,有些子问题被重复计算多次 如果能够保存已解决的子问题答案,在需要时再找出来已求得…...

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

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

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的大创管理系统
摘要 随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了大创管理系统的开发全过程。通过分析大创管理系统管理的不足,创建了一个计算机管理大创管理系统的方案。文章介绍了大创管理系统的系统分析部分&…...
常用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.对称二叉树
解决二叉树的问题,经常要习惯从递归角度思考 左子树/右子树是否具备某属性、是否属于什么类型(和题目要求的判断当前树是否xxx一样); 对左/右子树进行什么操作(和题目要求的对当前树的操作一样)。 226.翻转…...

word如何按照原本页面审阅文档
1 视图-阅读视图 2 视图,自己看,懒得打字了哈哈...
前端基础入门三大核心之HTML篇:探索WebAssembly —— 开启网页高性能应用新时代
前端基础入门三大核心之HTML篇:探索WebAssembly —— 开启网页高性能应用新时代 WebAssembly基础概念工作原理概览WebAssembly实战示例基本使用 安全性与性能优化防范漏洞实践实际工作中的使用技巧结语与讨论 随着Web技术的飞速发展,前端开发者面临越来越…...
NDIS小端口驱动(四)
NDIS中断相关 1. 注册和取消注册中断: 微型端口驱动程序调用 NdisMRegisterInterruptEx 来注册中断。 驱动程序分配并初始化 NDIS_MINIPORT_INTERRUPT_CHARACTERISTICS 结构,以指定中断特征和函数入口点,驱动程序将结构传递给 NdisMRegister…...
用户态网络缓冲区设计
基于数组实现的环形缓冲区: 优点 使用固定大小的连续空间做用户态缓冲区,利用了内存访问的局部性,可以提高缓存命中率,提高程序性能,在处理大量数据时,缓存的利用率对性能有着很大的影响 正是基于性能的…...
Linux运维工程师基础面试题整理(三)
Linux运维工程师基础面试题整理(三) 1. 文件inode号有什么用?2. 文件的权限怎么设置与管理?3. 如何SSH免密配置?4. 如何快速部署一个web服务?5. 如何更新Linux系统内核?6. centos中如何配置本地yum源?7.Linux 防火墙如何简单配置?8. 有哪些工具可以批量管理Linux服务器…...

基于单片机与传感器技术的汽车起动线路设计
摘 要:在以发动机为动力源的汽车中,起动系统承担起使发动机由非工作状态进入工作状态的重要作用,属于发动机的附属系统。在传统汽车起动系统的基础上提出将单片机与传感器技术运用到起动控制线路中,通过传感器采集发动机工作状态信…...
C#如何通过反射获取外部dll的函数
在C#中,你可以使用反射(Reflection)来加载外部的DLL(动态链接库)并获取其中的函数(在C#中通常称为方法)。但是,请注意,反射主要用于访问类型信息,并且对于非托…...

从零开始傅里叶变换
从零开始傅里叶变换 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 傅里叶变换…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...

虚拟机网络不通的问题(这里以win10的问题为主,模式NAT)
当我们网关配置好了,DNS也配置好了,最后在虚拟机里还是无法访问百度的网址。 第一种情况: 我们先考虑一下,网关的IP是否和虚拟机编辑器里的IP一样不,如果不一样需要更改一下,因为我们访问百度需要从物理机…...

【AI News | 20250609】每日AI进展
AI Repos 1、OpenHands-Versa OpenHands-Versa 是一个通用型 AI 智能体,通过结合代码编辑与执行、网络搜索、多模态网络浏览和文件访问等通用工具,在软件工程、网络导航和工作流自动化等多个领域展现出卓越性能。它在 SWE-Bench Multimodal、GAIA 和 Th…...