当前位置:网站首页>【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};
}
}
边栏推荐
- uni-app开发语音识别app,讲究的就是简单快速。
- Write macro with word
- Asemi rectifier bridge hd06 parameters, hd06 pictures, hd06 applications
- I'm doing open source in Didi
- CloudCompare——点云切片
- 手把手带你入门Apache伪静态的配置
- Solve Unicode decodeerror: 'GBK' codec can't decode byte 0xa2 in position 107
- Association modeling method in SAP segw transaction code
- RHCSA9
- SAP UI5 FlexibleColumnLayout 控件介绍
猜你喜欢
How to protect user privacy without password authentication?
初次使用腾讯云,解决只能使用webshell连接,不能使用ssh连接。
Write macro with word
MySQL 巨坑:update 更新慎用影响行数做判断!!!
RHCSA9
RHCSA1
Datapipeline was selected into the 2022 digital intelligence atlas and database development report of China Academy of communications and communications
Sorry, we can't open xxxxx Docx, because there is a problem with the content (repackaging problem)
Natural language processing series (I) introduction overview
Hiengine: comparable to the local cloud native memory database engine
随机推荐
Datapipeline was selected into the 2022 digital intelligence atlas and database development report of China Academy of communications and communications
RHCSA7
Halcon template matching actual code (I)
Hundred days to complete the open source task of the domestic database opengauss -- openguass minimalist version 3.0.0 installation tutorial
Introduction aux contrôles de la page dynamique SAP ui5
leetcode:221. 最大正方形【dp状态转移的精髓】
峰会回顾|保旺达-合规和安全双驱动的数据安全整体防护体系
APICloud Studio3 WiFi真机同步和WiFi真机预览使用说明
国内市场上的BI软件,到底有啥区别
使用 jMeter 对 SAP Spartacus 进行并发性能测试
Write macro with word
Reflection and imagination on the notation like tool
Cf:a. the third three number problem
A small talk caused by the increase of sweeping
RHCSA1
[cloud native] use of Nacos taskmanager task management
Laravel document reading notes -mews/captcha use (verification code function)
MySQL splits strings for conditional queries
Leetcode20. Valid parentheses
开发者,云原生数据库是未来吗?