LeetCode34:在排序数组中查找元素第一个和最后一个位置
原题地址:. - 力扣(LeetCode)
题目描述
给你一个按照非递减顺序排列的整数数组
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] <= 109nums是一个非递减数组-109 <= target <= 109
解题思路
二分查找:我们使用二分查找来查找目标值的左边界和右边界。在给定的有序数组中,使用二分查找可以减少搜索范围,从而达到 O(log n) 的时间复杂度。
- 左边界查找:我们在二分查找时,使用一个标志
lower来指示我们是查找目标值的左边界还是右边界。
- 如果
lower为true,则我们会在目标值的位置停止时继续往左移动,从而找到目标值的最左边位置。- 如果
lower为false,则我们会在目标值的位置停止时继续往右移动,直到目标值的右边界。返回结果:通过两次二分查找分别获取左边界和右边界的索引。如果左边界小于等于右边界,并且这两个位置上的值都等于目标值,则返回这两个索引;否则,返回
[-1, -1]。
源码实现
class Solution {public int[] searchRange(int[] nums, int target) {// 1. 使用二分查找找到目标值的左边界(lower = true)int leftIdx = binarySearch(nums, target, true);// 2. 使用二分查找找到目标值的右边界(lower = false),然后减去 1 获取实际的右边界int rightIdx = binarySearch(nums, target, false) - 1;// 3. 检查左边界和右边界是否有效,且这两个位置上的值是否为目标值if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {// 4. 返回目标值的左边界和右边界return new int[]{leftIdx, rightIdx};} // 5. 如果目标值不存在,返回 [-1, -1]return new int[]{-1, -1};}// 这里的 lower 参数用于控制是查找左边界(true)还是右边界(false)public int binarySearch(int[] nums, int target, boolean lower) {// 1. 初始化二分查找的左右边界int left = 0, right = nums.length - 1;// 2. 默认返回的答案是 nums.length,这样当目标值不存在时,能保证返回 [-1, -1]int ans = nums.length;while (left <= right) {int mid = (left + right) / 2;// 3. 根据目标值与中间值的比较来更新搜索范围// 4. 如果目标值小于中间值,或者是查找左边界时(lower = true)中间值大于等于目标值,// 则将搜索范围缩小到左半部分if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {// 5. 如果目标值大于中间值,则搜索范围缩小到右半部分left = mid + 1;}}// 6. 返回找到的索引位置(若没有找到,则返回 nums.length)return ans;}
}
复杂度分析
时间复杂度:
- 每次调用
binarySearch都是 O(log n),其中n是数组的长度。- 在
searchRange方法中,调用了两次binarySearch,一次查找左边界,另一次查找右边界。因此总时间复杂度为 O(log n)。空间复杂度:
- 该算法只使用了常量级的额外空间(除了返回结果数组),因此空间复杂度是 O(1)。
相关文章:
LeetCode34:在排序数组中查找元素第一个和最后一个位置
原题地址:. - 力扣(LeetCode) 题目描述 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须…...
汽车广告常见特效处理有哪些?
汽车广告作为展示汽车性能和外观的重要媒介,常常需要借助特效来增强视觉效果,吸引观众的注意力。以下是一篇关于汽车广告中常见特效处理的文章。 在竞争激烈的汽车市场中,广告不仅是推广产品的工具,更是艺术和科技的结合。特效技…...
Unexpected response code: 400解决
原因:Nginx配置错误,业务服务提供了 websocket 服务,基于 websocket 来实现报表数据的推送,客户在浏览器上查看报表,经过 http 代理将请求传递给后端服务。 解决方案 Nginx中增加websocket配置 location ~/websocket…...
世优科技携手人民中科打造AI数字人智能体助力智慧校园
近日,世优科技与人民中科携手,为中国劳动关系学院开发了一款AI数字人助手,不仅在校园内部承担日常问询、交互工作,还在学校的展厅中担任讲解员的角色,为师生们提供生动详尽的导览服务。 中国劳动关系学院作为中华全国总…...
Mac intel 安装IDEA激活时遇到问题 jetbrains.vmoptions.plist: Permission denied
激活时执行脚本, permission denied ➜ scripts ./install.sh ./install.sh: line 31: /Users/dry/Library/LaunchAgents/jetbrains.vmoptions.plist: Permission deniedjetbrains.vmoptions.plist 这个文件没权限,打开看了一下 install.sh 这…...
区块链应用第1讲:基于区块链的智慧货运平台
基于区块链的智慧货运平台 网络货运平台已经比较成熟,提供了给货源方提供找司机的交易匹配方案;其中包含这几个角色:货主、承运人(司机、车队长)、监管机构、平台。司机要想接单,依赖于多个中心化的第三方平台,且三方平…...
量化交易系统开发-实时行情自动化交易-风险控制
19年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 接下来继续说说风险控制模块࿰…...
深入探索 Seaborn:高级绘图的艺术与实践
引言 在数据科学领域,数据可视化是至关重要的一步。它不仅能够帮助我们更好地理解数据,还能有效地传达信息,支持决策过程。Seaborn 是一个基于 Matplotlib 的高级 Python 数据可视化库,它提供了许多高级绘图功能,使得…...
《现代工业经济和信息化》是什么级别的期刊?是正规期刊吗?能评职称吗?
问题解答: 问:《现代工业经济和信息化》是不是核心期刊? 答:不是,是知网收录的正规学术期刊。 问:《现代工业经济和信息化》级别? 答:省级。主管单位:山西省工业和…...
【TS】九天学会TS语法——2.TypeScript基本类型及变量声明
今天学习的内容是TypeScript 基本类型,包括 number, string, boolean, any, void 等,以及变量声明的方式和区别。 基本类型介绍变量声明(var, let, const)类型注解 开始学习 目录 引言 一、基本类型介绍 二、变量声明 1.概念解析 …...
html+js+css实现拖拽式便签留言
前些日子在网上冲浪时,看到一个便签式留言墙,让人耳目一新。心想这个看着不错,额想要。于是便开始搜寻是否有相应开源插件,想将其引入自己的博客中。但是搜寻了一圈,都没有符合预期的,要么功能不符合。有的功能符合&am…...
Redis原理篇——Redis数据结构
Redis原理篇 1、原理篇-Redis数据结构 1.1 Redis数据结构-动态字符串 我们都知道Redis中保存的Key是字符串,value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。 不过Redis没有直接使用C语言中的字符串,因为C语言字符串存…...
pdf文件预览和导出
抢先观看: window.URL.createObjectURL(): 用于根据传入的 Blob 对象或 File 对象生成一个临时的、可访问的 URL,仅在浏览器会话中有效,并且不会上传到服务器。 const url window.URL.createObjectURL(blob);Blob 对象: 是 …...
服务器数据恢复—RAID5阵列硬盘坏道掉线导致存储不可用的数据恢复案例
服务器存储数据恢复环境: 一台EqualLogic存储中有一组由16块SAS硬盘组建的RAID5阵列。上层划分了4个卷,采用VMFS文件系统,存放虚拟机文件。 服务器存储故障: 存储RAID5阵列中磁盘出现故障,有2块硬盘对应的指示灯亮黄灯…...
快速傅里叶变换(FFT)基础(附python实现)
对于非专业人士,傅里叶变换一直是一个神秘的武器,它可以分析出不同频域的信息,从时域转换到频域,揭示了信号的频率成分,对于数字信号处理(DSP)、图像、语音等数据来说,傅里叶变换是最…...
使用Docker-compose安装mysql5.7
1.首先选择一个目录用来存放docker-compse文件以及mysql的数据(例如logs、conf) cd /home mkdir mysql vi docker-compose.yml2.填写docker-compse.yml内容 version : 3 services:mysql:# 容器名(以后的控制都通过这个)container_name: mysql# 重启策略…...
如何管理PHP的API部署环境
管理PHP的API部署环境是一个涉及多个步骤和考虑因素的过程。以下是一些关键步骤和最佳实践,用于管理PHP的API部署环境: 一、选择合适的服务器和配置环境 选择服务器:根据API的访问量和性能需求,选择合适的服务器。可以选择物理服…...
web——sqliabs靶场——第一关
今天开始搞这个靶场,从小白开始一点点学习,加油!!!! 1.搭建靶场 注意点:1.php的版本问题,要用老版本 2.小p要先改数据库的密码,否则一直显示链接不上数据库 2.第一道题࿰…...
tartanvo ubuntu 20.04部署
1. 所有环境安装流程参考 2. 运行python3 tartanvo_node.py出现问题: ImportError: cannot import name int from numpy版本问题,卸载当前版本并更换版本: pip uninstall numpy pip install numpy1.22.4问题解决。 3. 采用2to3脚本将其代…...
SpringBoot整合Freemarker(三)
定义循环输出的宏 <#macro list title items> ${title?cap_first}:<#list items as x>*${x?cap_first}</#list> </#macro><list items["mouse", "elephant", "python"] title"Animals"/> 输出结果…...
SAP增强开发实战:如何用STARTING NEW TASK避免BAPI_TRANSACTION_COMMIT的坑?
SAP增强开发实战:如何用STARTING NEW TASK避免BAPI_TRANSACTION_COMMIT的坑? 在SAP标准增强开发中,当我们需要在出口函数里调用BAPI修改或创建业务单据时,总会遇到一个经典难题:如何在增强点安全地提交事务?…...
YOLOv11检测头架构演进与工程实现剖析
1. YOLOv11检测头架构演进解析 目标检测领域近年来发展迅猛,YOLO系列作为其中的佼佼者,每次迭代都带来显著突破。YOLOv11的检测头设计堪称该系列迄今为止最精妙的架构创新,它彻底重构了传统检测头的任务处理方式。我曾在多个工业项目中尝试过…...
保姆级教程:手把手教你用Python+Control库仿真PLL噪声传递函数
保姆级教程:手把手教你用PythonControl库仿真PLL噪声传递函数 锁相环(PLL)作为现代电子系统中的核心组件,其噪声特性直接影响通信质量、时钟精度等关键指标。但教科书上复杂的传递函数公式总让人望而生畏——直到你发现用几行Pyth…...
Claude Code能控制电脑了!开发全程不离终端,全无人值守模式启动
在官方演示中,只甩一个指令过去,AI就自己启动正在开发的应用,自己复现bug,自己修复,自己测试修复效果。 Claude Code上线Computer Use,直接捅破开发效率天花板。 在官方演示中,只甩一个指令过…...
Mustache错误处理与调试:7个常见问题排查清单
Mustache错误处理与调试:7个常见问题排查清单 【免费下载链接】mustache Logic-less Ruby templates. 项目地址: https://gitcode.com/gh_mirrors/mu/mustache Mustache是一款流行的无逻辑Ruby模板引擎,但开发者在实际使用中经常会遇到各种错误和…...
Transformer位置编码避坑指南:手把手教你用RoPE解决长文本外推难题(附Torch复现)
Transformer长文本处理实战:RoPE位置编码的工程化解决方案 在构建现代NLP系统时,处理长文本序列一直是Transformer架构面临的重大挑战。当序列长度超过模型预训练时的最大位置编码范围时,传统方法的性能会显著下降。这种现象在构建聊天机器人…...
4个维度解析Lenovo Legion Toolkit:游戏本性能管理的轻量革命
4个维度解析Lenovo Legion Toolkit:游戏本性能管理的轻量革命 【免费下载链接】LenovoLegionToolkit Lightweight Lenovo Vantage and Hotkeys replacement for Lenovo Legion laptops. 项目地址: https://gitcode.com/gh_mirrors/le/LenovoLegionToolkit 1.…...
5步释放Win11潜能:用Win11Debloat让系统性能提升60%的实战指南
5步释放Win11潜能:用Win11Debloat让系统性能提升60%的实战指南 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutte…...
Qt, C++数据类型扩展问题
Qt项目中ObjectDic类的类型扩展与代码优化 前言 在Qt项目开发中,我们经常会遇到需要处理不同类型数据的情况,尤其是当涉及到负数时,类型的选择就显得尤为重要。本文将详细介绍如何在Qt项目中扩展ObjectDic类的类型支持,从无符号整…...
让老旧Mac焕发新生:OpenCore Legacy Patcher完整指南
让老旧Mac焕发新生:OpenCore Legacy Patcher完整指南 【免费下载链接】OpenCore-Legacy-Patcher Experience macOS just like before 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 您的Mac是否被苹果官方"抛弃"&…...
