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

LeetCode【0034】在排序数组中查找元素的第一个和最后一个位置

本文目录

  • 1 中文题目
  • 2 求解方法:左右边界二分查找
    • 2.1 方法思路
    • 2.2 Python代码
    • 2.3 复杂度分析
  • 3 题目总结

1 中文题目

给定一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
输入:nums = [], target = 0
输出:[-1,-1]

提示:

  • 0 ≤ n u m s . l e n g t h ≤ 1 0 5 0 \leq nums.length \leq10^5 0nums.length105
  • − 1 0 9 ≤ n u m s [ i ] ≤ 1 0 9 -10^9 \leq nums[i] \leq 10^9 109nums[i]109
  • nums 是一个非递减数组
  • − 1 0 9 ≤ t a r g e t ≤ 1 0 9 -10^9 \leq target \leq 10^9 109target109

2 求解方法:左右边界二分查找

2.1 方法思路

方法核心

  • 使用两次改进的二分查找
  • 分别查找目标值的左右边界
  • 通过不同的条件控制边界的移动

实现步骤

(1)查找左边界的过程:

  • 初始化左右指针,分别指向数组的开始和结束
  • 在循环中计算中间位置
  • 当找到大于或等于目标值的元素时,记录该位置并继续往左找
  • 当找到小于目标值的元素时,需要往右找
  • 最终找到第一个等于目标值的位置
  • 需要判断是否越界以及是否真的找到了目标值

(2)查找右边界的过程:

  • 同样初始化左右指针
  • 在循环中不断更新中间位置
  • 当找到小于或等于目标值的元素时,继续往右找
  • 当找到大于目标值的元素时,需要往左找
  • 最终找到最后一个等于目标值的位置
  • 同样需要进行边界检查

方法示例

输入:nums = [5,7,7,8,8,10], target = 8左边界查找过程:
1. 初始状态:left = 0, right = 5mid = 2, nums[mid] = 7 < targetleft = mid + 1 = 32. 第二次迭代:left = 3, right = 5mid = 4, nums[mid] = 8 == targetright = mid - 1 = 33. 第三次迭代:left = 3, right = 3mid = 3, nums[mid] = 8 == targetright = mid - 1 = 24. 循环结束:left = 3,找到左边界右边界查找过程:
1. 初始状态:left = 0, right = 5mid = 2, nums[mid] = 7 < targetleft = mid + 1 = 32. 第二次迭代:left = 3, right = 5mid = 4, nums[mid] = 8 == targetleft = mid + 1 = 53. 第三次迭代:left = 5, right = 5mid = 5, nums[mid] = 10 > targetright = mid - 1 = 44. 循环结束:right = 4,找到右边界返回:[3, 4]

2.2 Python代码

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def binary_search_left(nums, target):# 寻找左边界的二分查找left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# 如果中间值大于或等于目标值,继续往左找if nums[mid] >= target:right = mid - 1# 如果中间值小于目标值,往右找else:left = mid + 1# 判断是否找到目标值if left >= len(nums) or nums[left] != target:return -1return leftdef binary_search_right(nums, target):# 寻找右边界的二分查找left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# 如果中间值小于或等于目标值,继续往右找if nums[mid] <= target:left = mid + 1# 如果中间值大于目标值,往左找else:right = mid - 1# 判断是否找到目标值if right < 0 or nums[right] != target:return -1return right# 特殊情况处理if not nums:return [-1, -1]# 分别查找左右边界left_bound = binary_search_left(nums, target)right_bound = binary_search_right(nums, target)return [left_bound, right_bound]

2.3 复杂度分析

  • 时间复杂度:O(log n)
    • 两次二分查找
    • 每次二分查找的时间复杂度为O(log n)
  • 空间复杂度:O(1)
    • 只使用常数额外空间
    • 不随输入规模增长

3 题目总结

题目难度:中等
数据结构:数组
应用算法:左右边界二次二分查找

相关文章:

LeetCode【0034】在排序数组中查找元素的第一个和最后一个位置

本文目录 1 中文题目2 求解方法&#xff1a;左右边界二分查找2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目 给定一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存…...

react-markdown内容宽度溢出和换行不生效问题

情景复现&#xff1a; 解决办法&#xff0c;添加样式进行限制 /* index.css */ .markdown-container {word-break: break-word; /* 强制长单词断行 */white-space: pre-wrap; /* 保留空白符序列&#xff0c;但是正常地进行换行 */overflow-wrap: break-word; /* 在长单词或…...

uniapp 上传 base64 图片

在图片裁剪时候返回的是base64文件 需要上传到obs一般出现在h5网页端 可以直接使用 js 原始解决 应该只可以在h5浏览器内使用 // 提取 Base64 编码部分 const base64Data e.tempFilePath.replace(/^data:image\/(\w);base64,/, ""); // 将 Base64 编码转换为 Arra…...

让Git走代理

有时候idea提交代码或者从github拉取代码&#xff0c;一直报错超时或者:Recv failure: Connection was reset,下面记录一下怎么让git走代理从而访问到github。 1.打开梯子 2.打开网络和Internet设置 3.设置代理 记住这个地址和端口 4.打开git bash终端 输入以下内容 git c…...

通义千问API调用测试 (colab-python,vue)

文章目录 代码&#xff08;来自官网&#xff09;colab中用python测试Qwen2.5在官网上查看并确定过期时间这里看到我的免费额度到25年5月在同一个页面&#xff0c;点击API示例 前端调用直接在前端调用的优缺点以vue为例&#xff08;代码是基于官网node.js的代码转换而来&#xf…...

H3C ER8300G2-X未授权导致信息泄露漏洞(CVE-2024-32238)

免责声明: 本文旨在提供有关特定漏洞的深入信息,帮助用户充分了解潜在的安全风险。发布此信息的目的在于提升网络安全意识和推动技术进步,未经授权访问系统、网络或应用程序,可能会导致法律责任或严重后果。因此,作者不对读者基于本文内容所采取的任何行为承担责任。读者在…...

随手记:简单实现纯前端文件导出(XLSX)

1.需求背景&#xff1a; 由于导入需要经过后端存储数据库&#xff0c;所以导入还是和后端联调 但是简单的前端导出有部分是可以直接给到用户 xlsx插件简介 xlsx插件&#xff08;通常指的是SheetJS/js-xlsx&#xff09;是一个强大的JavaScript库&#xff0c;它允许你在浏览器…...

SwiftUI 高级开发教程系列 - 第 3 章:数据持久化

在现代应用中,数据持久化是一项非常重要的功能,它使得应用的数据可以在重启后依然保留,提升用户体验。SwiftUI 提供了多种数据持久化方法,包括使用 UserDefaults 保存简单数据和 Core Data 进行更复杂的数据管理。本章将详细讲解这两种技术的用法,并展示如何在 SwiftUI 项…...

代码随想录第二十四天| 93.复原IP地址 78.子集 90.子集II

93. 复原IP地址 题目描述 给定一个只包含数字的字符串 s&#xff0c;复原它并返回所有可能的有效 IP 地址格式。 一个有效的 IP 地址 由四个整数部分组成&#xff0c;每部分的取值范围是 0-255&#xff0c;每个部分不能包含前导零。 解题思路 这道题目要求我们将一个数字字…...

Linux编程:基于 Unix Domain Socket 的进程/线程间通信实时性优化

文章目录 0. 引言1. 使用 epoll 边缘触发模式非不要不选择阻塞模式边缘触发&#xff08;ET&#xff09;模式优点示例 2. 使用实时调度策略3. CPU 绑定4. 使用无锁缓冲区5. 优化消息传递的大小和频率6. 使用 SO_RCVTIMEO 和 SO_SNDTIMEO7. 示例代码其他阅读 0. 引言 前几天被问…...

PET-文件包含-FINISHED

include发生错误报warning&#xff0c;继续执行。require发生错误直接error&#xff0c;不继续执行 无视扩展名&#xff0c;只要能解析&#xff0c;就能当可执行文件执行&#xff0c;哪怕文件后缀或没后缀 1 条件竞争 pass17 只需要知道tmp的路径。把xieshell.jpg上传&…...

《WebGL编程指南》书籍分享

在这个数字化时代&#xff0c;WebGL作为一门前沿的图形渲染技术&#xff0c;为网页带来了前所未有的交互体验。今天&#xff0c;我很荣幸向大家分享一本关于学习WebGL的书籍——《Webgl编程指南》 电子版下载链接: https://pan.baidu.com/s/1eTX2Y5ynYH0pUQRf0Jcbow?...

go T 泛型

目录 1、类型约束 2、泛型函数 3、泛型结构体 4、泛型接口 5、以接口作为类型约束 关键词&#xff1a;泛型、类型参数、类型约束 Go 语言在 1.18 版本引入了泛型&#xff08;Generics&#xff09;特性&#xff0c;可以编写更通用、可复用的代码&#xff0c;泛型可以用于&a…...

React的基础API介绍(二)

目录 useStateuseState 的基本原理1. 状态在函数组件中的引入2. useState 的工作机制3. Hook 状态与组件渲染 useState 的使用方法1. 基本用法2. 多个状态变量3. 更新状态 注意事项与最佳实践1. 状态更新可能是异步的2. 不要直接修改状态3. 更新对象或数组状态4. 避免闭包陷阱 …...

远程开发测试必看:如何在群晖NAS上运行网页版Ubuntu

文章目录 前言1. 下载Docker-Webtop镜像2. 运行Docker-Webtop镜像3. 本地访问网页版Linux系统4. 群晖NAS安装Cpolar工具5. 配置异地访问Linux系统6. 异地远程访问Linux系统7. 固定异地访问的公网地址 前言 本文将详细讲解如何在群晖NAS上部署docker-webtop&#xff0c;并利用c…...

JAVA题目笔记(十五)经典算法题

一、按要求排序 要求&#xff1a;定义数组并存储一些女朋友对象&#xff0c;利用Arrays中的sort方法进行排序 属性包括&#xff1a;姓名&#xff0c;年龄&#xff0c;身高 按照年龄大小进行排序&#xff0c;年龄一样按照身高排序&#xff0c;身高一样按照姓名字母进行排序。…...

「Mac玩转仓颉内测版8」入门篇8 - Cangjie函数与方法

本篇介绍Cangjie编程语言中的函数与方法&#xff0c;帮助理解如何通过函数封装重复操作&#xff0c;提升代码的复用性和可维护性。 关键词 Cangjie函数方法定义参数传递返回值模块化与复用性 一、什么是函数&#xff1f; 函数是一个代码块&#xff0c;用于接收参数、执行操作…...

2024最新版JavaScript逆向爬虫教程-------基础篇之Proxy与Reflect详解

目录 一、监听对象的操作二、Proxy基本使用2.1 创建空代理2.2 定义捕获器2.2.1 Proxy的set和get捕获器2.2.2 Proxy(handler)的13个捕获器 三、Reflect的作用3.1 Reflect的使用3.2 Reflect其余方法(9个)3.3 Proxy与Reflect中的receiver参数3.4 Reflect中的construct方法 ECMAScr…...

代码修改材质参数

1、 如何得到对象使用的材质 获取到对象的渲染器Renderer Mesh Renderer和Skinned Mesh Renderer都继承Renderer&#xff0c;可以用里式替换原则父类获取、装载子类对象 通过渲染器获取到对应材质 可以利用渲染器中的material或者sharedMaterial来获取物体的材质&#xff0…...

[C++11] 包装器 : function 与 bind 的原理及使用

文章目录 functionstd::function 的基本语法使用 std::function 包装不同的可调用对象function包装普通成员函数为什么要传入 this 指针参数&#xff1f;传入对象指针与传入对象实例的区别 例题 &#xff1a;150. 逆波兰表达式求值 - ⼒扣&#xff08;LeetCode&#xff09; bin…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...