【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一个位置|二分求下标
创始人
2024-05-16 16:16:46
0

在这里插入图片描述

🌱博主简介:大一计科生,努力学习Java中!热爱写博客~预备程序媛
📜所属专栏:LeetCode每日一题–进击大厂
✈往期博文回顾: 【Leetcode每日一题】35.搜素插入位置|二分查找数组下标
🕵️‍♂️近期目标:成为千粉小博主。
🌺“再牛的程序员也是从小白开始,既然开始了,就全身心投入去学习技术”

34. 在排序数组中查找元素的第一个和最后一个位置
在这里插入图片描述

解题思路

  • 题型:数组、二分查找(变式)—寻找第1个等于目标值的元素&寻找最后1个等于目标值的元素
  • 关键:二分查找的关键点就是–逐渐缩小搜索区间(若搜索区间没有被缩小,则会二分失败,导致死循环)
  • 思路
    1.确定答案可能取值区间[left,right]—[0,len-1]
    2.left = 0;right = array.length-1;

    3.while(left(不考虑所谓的什么闭区间,就仅仅代表它本身的含义:
    4.🌟分情况讨论!分别找出:
    • 第1个等于target的元素
    • 最后1个等于target的元素

🙋‍♀️根据我自己的理解画的图:

在这里插入图片描述

代码实现:

class Solution {public int[] searchRange(int[] nums, int target) {int len=nums.length;if(len==0){return new int[]{-1,-1};//数组长度为0}int firstPosition = findFisrtPosition(nums,target);if(firstPosition==-1){return new int[]{-1,-1};}int lastPosition = findLastPosition(nums,target);return new int[]{firstPosition,lastPosition};}private int findFisrtPosition(int[] nums,int target){int left=0;int right=nums.length-1;while(leftint mid=left+(right-left)/2;//防止溢出if(nums[mid]>=target){right=mid;//下一轮搜索区间为[left,mid]}else{left=mid+1;}}if(nums[left]!=target){//目标元素不在数组中return -1;}return right;}private int findLastPosition(int[] nums,int target){int left=0;int right=nums.length-1;while(leftint mid=left+(right-left+1)/2;//防止溢出if(nums[mid]<=target){left=mid;//下一轮搜索区间为[mid,right]}else{right=mid-1;}}  return left;}
}
  • 细节
    1.如果数组长度为0,直接返回[-1,-1]
    2.如果firstPosition找不到,直接返回[-1,-1]
    3.寻找第一个等于targer元素时:退出循环后不能判断此区间的元素是target!需要再次判断!
    4.🌟这里findLastPosition中:mid = left+(right-left+1)/2中的+1是不能省的!目的还是当只剩两个元素时,mid指针指向的是后一个元素,按照[left,mid-1]、[mid,right]来分才有可能缩小区间。(避免死循环的关键)
  • 🙇‍♀️建立此专栏的初衷是为了监督自己每天认真刷一个题,积少成多。并把自己每次刷题的思路、收获以博文的形式分享出来,帮助更多人,以及方便后续复习。如果有兴趣的同学可以订阅此专栏,我们一起刷题,一起交流,进步和学习!专栏:LeetCode每日一题–进击大厂

在这里插入图片描述

相关内容

热门资讯

安卓子系统windows11,... 你知道吗?最近科技圈可是炸开了锅,因为安卓子系统在Windows 11上的兼容性成了大家热议的话题。...
电脑里怎么下载安卓系统,电脑端... 你有没有想过,你的电脑里也能装上安卓系统呢?没错,就是那个让你手机不离手的安卓!今天,就让我来带你一...
索尼相机魔改安卓系统,魔改系统... 你知道吗?最近在摄影圈里掀起了一股热潮,那就是索尼相机魔改安卓系统。这可不是一般的改装,而是让这些专...
安卓系统哪家的最流畅,安卓系统... 你有没有想过,为什么你的手机有时候像蜗牛一样慢吞吞的,而别人的手机却能像风一样快?这背后,其实就是安...
安卓最新系统4.42,深度解析... 你有没有发现,你的安卓手机最近是不是有点儿不一样了?没错,就是那个一直在默默更新的安卓最新系统4.4...
android和安卓什么系统最... 你有没有想过,你的安卓手机到底是用的是什么系统呢?是不是有时候觉得手机卡顿,运行缓慢,其实跟这个系统...
平板装安卓xp系统好,探索复古... 你有没有想过,把安卓系统装到平板上,再配上XP系统,这会是怎样一番景象呢?想象一边享受着安卓的便捷,...
投影仪装安卓系统,开启智能投影... 你有没有想过,家里的老式投影仪也能焕发第二春呢?没错,就是那个曾经陪你熬夜看电影的“老伙计”,现在它...
安卓系统无线车载carplay... 你有没有想过,开车的时候也能享受到苹果设备的便利呢?没错,就是那个让你在日常生活中离不开的iOS系统...
谷歌安卓8系统包,系统包解析与... 你有没有发现,手机更新换代的速度简直就像坐上了火箭呢?这不,最近谷歌又发布了安卓8系统包,听说这个新...
微软平板下软件安卓系统,开启全... 你有没有想过,在微软平板上也能畅享安卓系统的乐趣呢?没错,这就是今天我要跟你分享的神奇故事。想象你手...
coloros是基于安卓系统吗... 你有没有想过,手机里的那个色彩斑斓的界面,背后其实有着一个有趣的故事呢?没错,我要说的就是Color...
安卓神盾系统应用市场,一站式智... 你有没有发现,手机里的安卓神盾系统应用市场最近可是火得一塌糊涂啊!这不,我就来给你好好扒一扒,看看这...
黑莓平板安卓系统升级,解锁无限... 亲爱的读者们,你是否还记得那个曾经风靡一时的黑莓手机?那个标志性的全键盘,那个独特的黑莓体验,如今它...
安卓文件系统采用华为,探索高效... 你知道吗?最近安卓系统在文件管理上可是有了大动作呢!华为这个科技巨头,竟然悄悄地给安卓文件系统来了个...
深度系统能用安卓app,探索智... 你知道吗?现在科技的发展真是让人惊叹不已!今天,我要给你揭秘一个超级酷炫的话题——深度系统能用安卓a...
安卓系统的分区类型,深度解析存... 你有没有发现,你的安卓手机里藏着不少秘密?没错,就是那些神秘的分区类型。今天,就让我带你一探究竟,揭...
安卓系统铠无法兑换,揭秘无法兑... 最近是不是有很多小伙伴在玩安卓系统的游戏,突然发现了一个让人头疼的问题——铠无法兑换!别急,今天就来...
汽车安卓系统崩溃怎么刷,一键刷... 亲爱的车主朋友们,你是否曾遇到过汽车安卓系统崩溃的尴尬时刻?手机系统崩溃还能重启,但汽车系统崩溃了,...
miui系统可以刷安卓p系统吗... 亲爱的手机控们,你是否对MIUI系统情有独钟,同时又对安卓P系统的新鲜功能垂涎欲滴?今天,就让我带你...