当前位置:网站首页>【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};
}
}
边栏推荐
猜你喜欢
Get to know linkerd project for the first time
Datapipeline was selected into the 2022 digital intelligence atlas and database development report of China Academy of communications and communications
将函数放在模块中
Natural language processing series (I) introduction overview
A specific example of ABAP type and EDM type mapping in SAP segw transaction code
Asemi rectifier bridge hd06 parameters, hd06 pictures, hd06 applications
Lepton 无损压缩原理及性能分析
Navigation property and entityset usage in SAP segw transaction code
爱可生SQLe审核工具顺利完成信通院‘SQL质量管理平台分级能力’评测
Hiengine: comparable to the local cloud native memory database engine
随机推荐
Run, open circuit
Association modeling method in SAP segw transaction code
初识Linkerd项目
Sorry, we can't open xxxxx Docx, because there is a problem with the content (repackaging problem)
How do e-commerce sellers refund in batches?
事务的基本特性和隔离级别
mysql econnreset_Nodejs 套接字报错处理 Error: read ECONNRESET
峰会回顾|保旺达-合规和安全双驱动的数据安全整体防护体系
UnicodeDecodeError: ‘utf-8‘ codec can‘t decode byte 0xe6 in position 76131: invalid continuation byt
APICloud Studio3 API管理与调试使用教程
[cloud native] event publishing and subscription in Nacos -- observer mode
ASEMI整流桥HD06参数,HD06图片,HD06应用
Changing JS code has no effect
insmod 提示 Invalid module format
[Nacos cloud native] the first step of reading the source code is to start Nacos locally
Four common problems of e-commerce sellers' refund and cash return, with solutions
Introduction aux contrôles de la page dynamique SAP ui5
How to realize batch sending when fishing
RHCSA2
跨平台(32bit和64bit)的 printf 格式符 %lld 输出64位的解决方式