当前位置:网站首页>【Hot100】34. 在排序数组中查找元素的第一个和最后一个位置
【Hot100】34. 在排序数组中查找元素的第一个和最后一个位置
2022-07-05 12:56:00 【王六六的IT日常】
34. 在排序数组中查找元素的第一个和最后一个位置
中等题
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。
请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
题解:
在一个范围内,查找一个数字,要求找到这个元素的开始位置和结束位置,这个范围内的数字都是单调递增的,即具有单调性质,因此可以使用二分来做。
两次二分,第一次二分查找第一个t>=target的位置,第二次二分查找最后一个t<=target的位置。
查找成功则返回两个位置下标,否则返回[-1,-1]。
- 模板一:当我们将区间[l, r]划分成[l,mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1,计算mid时不需要加1,即mid=(l+r)/2。
- 模板二:当我们将区间[l, r]划分成[l,mid−1]和[mid,r]时,其更新操作是r=mid−1或者l=mid,此时为了防止死循环,计算mid时需要加1,即mid=(l+r+1)/2。
注意:
当左边界要更新为l = mid
时,就令 mid =(l + r + 1)/2
,相当于上取整,此时就不会因为r取特殊值 r = l + 1
而陷入死循环了。
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) {
return new int[]{
-1,-1};
}
int l = 0, r = nums.length - 1; //二分范围
while( l < r) //查找元素的开始位置
{
int mid = (l + r )/2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if( nums[r] != target) {
return new int[]{
-1,-1}; //查找失败
}
int L = r;
l = 0;
r = nums.length - 1; //二分范围
while( l < r) //查找元素的结束位置
{
int mid = (l + r + 1)/2;
if(nums[mid] <= target ) l = mid;
else r = mid - 1;
}
return new int[]{
L,r};
}
}
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0){
return new int[]{
-1,-1};
}
int l = 0, r = nums.length - 1; //二分范围 左闭右闭
//查找元素的开始位置
while( l < r){
int mid = (l + r )/2;
if(nums[mid] >= target){
r = mid;
} else{
l = mid + 1;
}
}
if( nums[r] != target){
return new int[]{
-1,-1}; //查找失败
}
int L = r;
l = 0; r = nums.length - 1; //二分范围
//查找元素的结束位置
while( l < r)
{
int mid = (l + r + 1)/2; //注意
if(nums[mid] <= target ){
l = mid;
} else {
r = mid - 1;
}
}
return new int[]{
L,r};
}
}
边栏推荐
- Realize the addition of all numbers between 1 and number
- RHCSA1
- How to realize batch sending when fishing
- Principle and configuration of RSTP protocol
- Reverse Polish notation
- ABAP editor in SAP segw transaction code
- 单独编译内核模块
- 关于 SAP UI5 getSAPLogonLanguage is not a function 的错误消息以及 API 版本的讨论
- Rocky basics 1
- MySQL splits strings for conditional queries
猜你喜欢
Why is your next computer a computer? Explore different remote operations
Small case of function transfer parameters
Principle and configuration of RSTP protocol
Le rapport de recherche sur l'analyse matricielle de la Force des fournisseurs de RPA dans le secteur bancaire chinois en 2022 a été officiellement lancé.
《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
CF:A. The Third Three Number Problem【关于我是位运算垃圾这个事情】
RHCAS6
无密码身份验证如何保障用户隐私安全?
国际自动机工程师学会(SAE International)战略投资几何伙伴
量价虽降,商业银行结构性存款为何受上市公司所偏爱?
随机推荐
Word document injection (tracking word documents) incomplete
Solve Unicode decodeerror: 'GBK' codec can't decode byte 0xa2 in position 107
RHCSA1
Binder通信过程及ServiceManager创建过程
RHCSA7
事务的基本特性和隔离级别
峰会回顾|保旺达-合规和安全双驱动的数据安全整体防护体系
关于 SAP UI5 getSAPLogonLanguage is not a function 的错误消息以及 API 版本的讨论
Halcon template matching actual code (I)
Lepton 无损压缩原理及性能分析
Yyds dry inventory JS intercept file suffix
阿里云SLB负载均衡产品基本概念与购买流程
ABAP editor in SAP segw transaction code
Halcon 模板匹配实战代码(一)
Pycharm installation third party library diagram
【Nacos云原生】阅读源码第一步,本地启动Nacos
前缀、中缀、后缀表达式「建议收藏」
leetcode:221. 最大正方形【dp状态转移的精髓】
Get to know linkerd project for the first time
Taobao product details API | get baby SKU, main map, evaluation and other API interfaces