LeetCode 算法:在排序数组中查找元素的第一个和最后一个位置 c++
原题链接🔗:在排序数组中查找元素的第一个和最后一个位置
难度:中等⭐️⭐️
题目
给你一个按照非递减顺序排列的整数数组 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]
提示:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
二分查找
-
二分查找(Binary Search),也称为折半搜索,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较:
- 如果目标值等于中间元素,搜索成功,返回该位置。
- 如果目标值小于中间元素,搜索范围缩小至数组的左半部分。
- 如果目标值大于中间元素,搜索范围缩小至数组的右半部分。
- 这个过程将不断重复,直到找到目标值或者搜索范围为空为止。
-
以下是二分查找算法的一般步骤:
-
初始化:设置两个指针,一个指向数组的起始位置(通常记为
left
),另一个指向数组的结束位置(通常记为right
)。 -
循环条件:当
left
小于等于right
时,继续循环。 -
计算中间位置:计算
left
和right
之间的中间位置mid
,通常使用(left + right) / 2
。 -
比较与调整:
- 如果
nums[mid]
等于目标值,根据需要返回mid
或继续搜索以找到更精确的位置。 - 如果
nums[mid]
大于目标值,将right
调整为mid - 1
。 - 如果
nums[mid]
小于目标值,将left
调整为mid + 1
。
- 如果
-
循环结束:如果
left
大于right
,则表示目标值不在数组中,返回一个特定的值(通常是 -1)表示未找到。
-
-
二分查找的效率非常高,时间复杂度为 O(log n),其中 n 是数组的长度。然而,它要求数组是有序的,并且只能应用于一维有序数组。
-
下面是一个简单的 C++ 实现示例:
int binarySearch(const std::vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2; // 防止溢出if (nums[mid] == target) {return mid; // 找到目标值} else if (nums[mid] < target) {left = mid + 1; // 搜索右半部分} else {right = mid - 1; // 搜索左半部分}}return -1; // 未找到目标值
}
这个函数会返回目标值在数组中的索引,如果目标值不在数组中,则返回 -1。
题解
- 解题思路:
LeetCode 上的这个问题通常被称为“Find First and Last Position of Element in Sorted Array”,题目编号为 34。这个问题可以通过二分查找算法来解决,因为数组是已经排序的。
以下是解决这个问题的一般思路:
理解问题:首先,你需要理解问题的要求,即在一个升序排序的数组中找到给定元素的第一个和最后一个位置。
二分查找:由于数组是有序的,你可以使用二分查找来找到目标元素的索引。二分查找的基本思想是将数组分成两半,比较中间元素与目标值,然后根据比较结果决定是继续在左半部分查找还是右半部分查找。
找到第一个位置:使用二分查找,但需要稍作修改以找到第一个位置。在每次迭代中,如果中间元素等于目标值,你不能立即返回这个位置,因为可能还有更小的索引也是目标值。你需要向左半边继续查找。
找到最后一个位置:同样使用二分查找,但这次如果中间元素等于目标值,你需要向右半边继续查找,因为可能还有更大的索引也是目标值。
边界条件:在查找过程中,需要处理数组的边界条件,确保不会访问数组之外的索引。
- c++ demo:
#include <vector>
#include <iostream>// 二分查找函数,用于找到目标值的索引
int binarySearch(const std::vector<int>& nums, int target, bool findFirst) {int left = 0, right = nums.size() - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {result = mid; // 记录找到的位置if (findFirst) {right = mid - 1; // 向左查找第一个位置}else {left = mid + 1; // 向右查找最后一个位置}}else if (nums[mid] < target) {left = mid + 1;}else {right = mid - 1;}}return result;
}// 主函数,用于找到元素的第一个和最后一个位置
std::vector<int> findFirstAndLastPosition(const std::vector<int>& nums, int target) {int first = binarySearch(nums, target, true); // 找到第一个位置int last = binarySearch(nums, target, false); // 找到最后一个位置return { first, last };
}int main() {std::vector<int> nums = { 5, 7, 7, 8, 8, 10 };int target = 8;std::vector<int> positions = findFirstAndLastPosition(nums, target);std::cout << "First position: " << positions[0] << std::endl;std::cout << "Last position: " << positions[1] << std::endl;return 0;
}
- 输出结果:
First position: 3
Last position: 4
- 代码仓库地址:findFirstAndLastPosition
相关文章:
LeetCode 算法:在排序数组中查找元素的第一个和最后一个位置 c++
原题链接🔗:在排序数组中查找元素的第一个和最后一个位置 难度:中等⭐️⭐️ 题目 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标…...

会话存储、本地存储,路由导航守卫、web会话跟踪、JWT生成token、axios请求拦截、响应拦截
1、会话存储、本地存储 前端浏览器中存储用户信息,会话存储、本地存储、cookie 会话存储(sessionStorage):会话期间存储,关闭浏览器后,数据就会销毁 sessionStorage.setItem("account",resp.d…...
strcmp库函数原型
int strcmp(const char *str1, const char *str2) {unsigned const char *s1 (unsigned const char *) str1;unsigned const char *s2 (unsigned const char *) str2;while (*s1 && *s1 *s2) {s1;s2;}return *s1 - *s2; }while (*s1 && *s1 *s2) 一直循环&…...
在 Vue.js 项目中延迟加载子组件
在 Vue.js 中,当父组件渲染时,子组件的生命周期钩子函数会立即执行,即使这些子组件并未显示。这是因为 Vue.js 会在渲染父组件时实例化所有引用的子组件。为了避免不必要的函数执行,我们可以通过使用 v-if 指令和异步组件延迟加载…...
何时会用到设计模式、七大设计原则介绍
以下关于b站尚硅谷相关设计模式视频的总结 设计模式的重要性: 代码重用性(相同的代码,不用编写很多次)、 可读性(编程规范,便于其他程序员阅读和理解)、 可扩展性(增加新功能时&am…...

编程语言发展历史:赋值与相等运算符的变迁历程
本文摘取自笔者书稿《编程语言发展历史》 赋值运算符是编程语言最基础的运算符,其发展历史也非常有趣。最早的赋值语句就是使用等号“”来表示,一些语言为了让赋值运算在数学形式上更加严谨(形如“x x 1”的表达式在数学上不成立࿰…...

求职Leetcode题目(2)
1.柱状图中最大的矩形 据说这是2024年字节二面的题目,我感觉这道题跟接雨水有点类似,最重要的思路还是要找到什么时候能形成矩形的这么个情况,某个范围的矩形的高度,是由最短的柱形来决定的。 我们先整理一下,解决这道…...
深入探索 Postman:使用 API 性能测试优化你的 Web 服务
引言 在当今快速发展的互联网时代,Web 服务的性能至关重要。API 作为服务之间的桥梁,其性能直接影响到整个应用的响应速度和用户体验。Postman,作为一个多功能的 API 开发工具,提供了强大的性能测试功能,帮助开发者评…...

校车购票小程序的设计
管理员账户功能包括:系统首页,个人中心,学生管理,我的乘车信息管理,车辆信息管理,座位管理,系统管理 微信端账号功能包括:系统首页,车辆信息,我的 开发系统…...

拯救数据危机!2024年最受欢迎的数据恢复软件评测
现在大家快速传输资料的方式都变成了电子档,有些数据是存储在电脑上,有些存储在手机,有的存储在U盘甚至其他一些电子设备上。电子设备存储数据方便,丢失数据也总在意料之外。很多时候我们多学会一个工具,比如转转大师数…...

记一次因为在html两个地方引入vue.js导致组件注入失败的问题
这个问题我遇到两次了,是在恼火,不对,三次了,我如果不做这个笔记,我确定我还会遇到第三次。 尾部这个去掉就行 因为头部有了 遇到这种bu g好恼火,解决了又怎么样呢?重蹈覆辙的滋味不好受...
Postman中的智慧重试:API测试用例的错误处理与重试逻辑设置
Postman中的智慧重试:API测试用例的错误处理与重试逻辑设置 在API测试过程中,错误处理和重试逻辑是确保测试准确性和可靠性的重要环节。Postman提供了多种功能来处理测试中可能出现的错误,并允许自定义重试逻辑以适应不同的测试场景。本文将…...
docker部署本地词向量模型
开源项目:GitHub - huggingface/text-embeddings-inference: A blazing fast inference solution for text embeddings models 1. 下载词向量模型 参考我的另一篇博客:langchain 加载本地词向量模型 2. 部署词向量模型 就三行命令 model/data/BAAI/…...

接口自动化中对于文件上传的处理方法
正常的接口自动化基本都是json的格式,对于文件上传是一种特殊的格式是表单格式针对这种表单格式在接口自动化中怎么处理,主要通过工作中使用的一个实际的例子进行分享 举例:web上需要导入一个文件实现相关的功能,主要通过两个接口…...

Java高频面试题分享
文章目录 1. 策略模式怎么控制策略的选取1.1 追问:如果有100种策略呢?1.2 追问:什么情况下初始化Map 2. 什么是索引?什么时候用索引?2.1 追问:怎么判断系统什么时候用量比较少2.2 追问:如何实时…...

kvm虚拟化平台部署
kvm虚拟化平台部署 kvm概念简介 kvm自linux2.6版本以后就整合到内核中,因此可以看做是一个原生架构. kvm虚拟化架构 硬件底层提供物理层面的硬件支持 linux(host),就相当于这个架构中的宿主机,上面运行了多个虚拟机。…...
利用arthas热更新class文件
利用arthas热更新class文件 背景:发现一个bug,家里难以复现,需要在现场环境更新几行代码验证。 arthas-boot version: 3.7.1 java -jar arthas-boot.jar启动arthas 1、利用arthas的sc命令查找确定类名称 sc com.**2、反编译为java文件 …...

天机学堂 第四天 高并发优化总结
前端每隔15秒就发起一次请求,将播放记录写入数据库。 但问题是,提交播放记录的业务太复杂了,其中涉及到大量的数据库操作: 如何进行优化 单机并发能力 变同步为异步 合并写请求 提高单机并发:优化SQL,尽…...

Canva收购Leonardo.ai,增强生成式AI技术能力
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...

前端练习<HtmlCSS>——照片墙(附完整代码及实现效果)
这个小练习也来源于b站up小K师兄,大家可以通过下面的链接学习哦~up讲的非常详细。 纯CSS写一个简单酷炫的照片墙效果~ 先看一下这个照片墙的效果: 1.鼠标没有放到图片上时,照片同比例,每张照片都有倒影的效果。 2.然…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...