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

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

二分查找

  1. 二分查找(Binary Search),也称为折半搜索,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较:

    1. 如果目标值等于中间元素,搜索成功,返回该位置。
    2. 如果目标值小于中间元素,搜索范围缩小至数组的左半部分。
    3. 如果目标值大于中间元素,搜索范围缩小至数组的右半部分。
    4. 这个过程将不断重复,直到找到目标值或者搜索范围为空为止。
  2. 以下是二分查找算法的一般步骤:

    1. 初始化:设置两个指针,一个指向数组的起始位置(通常记为 left),另一个指向数组的结束位置(通常记为 right)。

    2. 循环条件:当 left 小于等于 right 时,继续循环。

    3. 计算中间位置:计算 leftright 之间的中间位置 mid,通常使用 (left + right) / 2

    4. 比较与调整

      • 如果 nums[mid] 等于目标值,根据需要返回 mid 或继续搜索以找到更精确的位置。
      • 如果 nums[mid] 大于目标值,将 right 调整为 mid - 1
      • 如果 nums[mid] 小于目标值,将 left 调整为 mid + 1
    5. 循环结束:如果 left 大于 right,则表示目标值不在数组中,返回一个特定的值(通常是 -1)表示未找到。

  3. 二分查找的效率非常高,时间复杂度为 O(log n),其中 n 是数组的长度。然而,它要求数组是有序的,并且只能应用于一维有序数组。

  4. 下面是一个简单的 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。

题解

  1. 解题思路:

LeetCode 上的这个问题通常被称为“Find First and Last Position of Element in Sorted Array”,题目编号为 34。这个问题可以通过二分查找算法来解决,因为数组是已经排序的。

以下是解决这个问题的一般思路:

  • 理解问题:首先,你需要理解问题的要求,即在一个升序排序的数组中找到给定元素的第一个和最后一个位置。

  • 二分查找:由于数组是有序的,你可以使用二分查找来找到目标元素的索引。二分查找的基本思想是将数组分成两半,比较中间元素与目标值,然后根据比较结果决定是继续在左半部分查找还是右半部分查找。

  • 找到第一个位置:使用二分查找,但需要稍作修改以找到第一个位置。在每次迭代中,如果中间元素等于目标值,你不能立即返回这个位置,因为可能还有更小的索引也是目标值。你需要向左半边继续查找。

  • 找到最后一个位置:同样使用二分查找,但这次如果中间元素等于目标值,你需要向右半边继续查找,因为可能还有更大的索引也是目标值。

  • 边界条件:在查找过程中,需要处理数组的边界条件,确保不会访问数组之外的索引。

  1. 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

  1. 代码仓库地址:findFirstAndLastPosition

相关文章:

LeetCode 算法:在排序数组中查找元素的第一个和最后一个位置 c++

原题链接&#x1f517;&#xff1a;在排序数组中查找元素的第一个和最后一个位置 难度&#xff1a;中等⭐️⭐️ 题目 给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标…...

会话存储、本地存储,路由导航守卫、web会话跟踪、JWT生成token、axios请求拦截、响应拦截

1、会话存储、本地存储 前端浏览器中存储用户信息&#xff0c;会话存储、本地存储、cookie 会话存储&#xff08;sessionStorage&#xff09;&#xff1a;会话期间存储&#xff0c;关闭浏览器后&#xff0c;数据就会销毁 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 中&#xff0c;当父组件渲染时&#xff0c;子组件的生命周期钩子函数会立即执行&#xff0c;即使这些子组件并未显示。这是因为 Vue.js 会在渲染父组件时实例化所有引用的子组件。为了避免不必要的函数执行&#xff0c;我们可以通过使用 v-if 指令和异步组件延迟加载…...

何时会用到设计模式、七大设计原则介绍

以下关于b站尚硅谷相关设计模式视频的总结 设计模式的重要性&#xff1a; 代码重用性&#xff08;相同的代码&#xff0c;不用编写很多次&#xff09;、 可读性&#xff08;编程规范&#xff0c;便于其他程序员阅读和理解&#xff09;、 可扩展性&#xff08;增加新功能时&am…...

编程语言发展历史:赋值与相等运算符的变迁历程

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

求职Leetcode题目(2)

1.柱状图中最大的矩形 据说这是2024年字节二面的题目&#xff0c;我感觉这道题跟接雨水有点类似&#xff0c;最重要的思路还是要找到什么时候能形成矩形的这么个情况&#xff0c;某个范围的矩形的高度&#xff0c;是由最短的柱形来决定的。 我们先整理一下&#xff0c;解决这道…...

深入探索 Postman:使用 API 性能测试优化你的 Web 服务

引言 在当今快速发展的互联网时代&#xff0c;Web 服务的性能至关重要。API 作为服务之间的桥梁&#xff0c;其性能直接影响到整个应用的响应速度和用户体验。Postman&#xff0c;作为一个多功能的 API 开发工具&#xff0c;提供了强大的性能测试功能&#xff0c;帮助开发者评…...

校车购票小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;我的乘车信息管理&#xff0c;车辆信息管理&#xff0c;座位管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;车辆信息&#xff0c;我的 开发系统…...

拯救数据危机!2024年最受欢迎的数据恢复软件评测

现在大家快速传输资料的方式都变成了电子档&#xff0c;有些数据是存储在电脑上&#xff0c;有些存储在手机&#xff0c;有的存储在U盘甚至其他一些电子设备上。电子设备存储数据方便&#xff0c;丢失数据也总在意料之外。很多时候我们多学会一个工具&#xff0c;比如转转大师数…...

记一次因为在html两个地方引入vue.js导致组件注入失败的问题

这个问题我遇到两次了&#xff0c;是在恼火&#xff0c;不对&#xff0c;三次了&#xff0c;我如果不做这个笔记&#xff0c;我确定我还会遇到第三次。 尾部这个去掉就行 因为头部有了 遇到这种bu g好恼火&#xff0c;解决了又怎么样呢&#xff1f;重蹈覆辙的滋味不好受...

Postman中的智慧重试:API测试用例的错误处理与重试逻辑设置

Postman中的智慧重试&#xff1a;API测试用例的错误处理与重试逻辑设置 在API测试过程中&#xff0c;错误处理和重试逻辑是确保测试准确性和可靠性的重要环节。Postman提供了多种功能来处理测试中可能出现的错误&#xff0c;并允许自定义重试逻辑以适应不同的测试场景。本文将…...

docker部署本地词向量模型

开源项目&#xff1a;GitHub - huggingface/text-embeddings-inference: A blazing fast inference solution for text embeddings models 1. 下载词向量模型 参考我的另一篇博客&#xff1a;langchain 加载本地词向量模型 2. 部署词向量模型 就三行命令 model/data/BAAI/…...

接口自动化中对于文件上传的处理方法

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

Java高频面试题分享

文章目录 1. 策略模式怎么控制策略的选取1.1 追问&#xff1a;如果有100种策略呢&#xff1f;1.2 追问&#xff1a;什么情况下初始化Map 2. 什么是索引&#xff1f;什么时候用索引&#xff1f;2.1 追问&#xff1a;怎么判断系统什么时候用量比较少2.2 追问&#xff1a;如何实时…...

kvm虚拟化平台部署

kvm虚拟化平台部署 kvm概念简介 kvm自linux2.6版本以后就整合到内核中&#xff0c;因此可以看做是一个原生架构. kvm虚拟化架构 硬件底层提供物理层面的硬件支持 linux&#xff08;host&#xff09;&#xff0c;就相当于这个架构中的宿主机&#xff0c;上面运行了多个虚拟机。…...

利用arthas热更新class文件

利用arthas热更新class文件 背景&#xff1a;发现一个bug&#xff0c;家里难以复现&#xff0c;需要在现场环境更新几行代码验证。 arthas-boot version: 3.7.1 java -jar arthas-boot.jar启动arthas 1、利用arthas的sc命令查找确定类名称 sc com.**2、反编译为java文件 …...

天机学堂 第四天 高并发优化总结

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

Canva收购Leonardo.ai,增强生成式AI技术能力

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

前端练习<HtmlCSS>——照片墙(附完整代码及实现效果)

这个小练习也来源于b站up小K师兄&#xff0c;大家可以通过下面的链接学习哦~up讲的非常详细。 纯CSS写一个简单酷炫的照片墙效果&#xff5e; 先看一下这个照片墙的效果&#xff1a; 1.鼠标没有放到图片上时&#xff0c;照片同比例&#xff0c;每张照片都有倒影的效果。 2.然…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

Netty自定义协议解析

目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...