【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每日一题–进击大厂

在这里插入图片描述

相关内容

热门资讯

安卓系统苹果手机识别,跨界融合... 你知道吗?在科技飞速发展的今天,手机已经成为了我们生活中不可或缺的一部分。而说到手机,安卓系统和苹果...
harmonyos系统是不是安... 亲爱的读者,你是否曾好奇过HarmonyOS系统与安卓系统之间的关系?是不是安卓的“亲戚”?今天,就...
手机怎么装系统安卓,安卓系统安... 手机卡顿了?想给安卓系统来个大变身?别急,跟着我一步步来,保证让你的手机焕然一新!一、准备工作在开始...
安卓Linux系统内网穿透,A... 你有没有想过,你的安卓手机里那些看似普通的APP,其实可能正在悄悄地帮你打通网络世界的任督二脉呢?没...
win怎么安装安卓系统,Win... 亲爱的读者,你是不是对Win系统上的安卓应用垂涎已久,但又苦于不知道如何安装安卓系统呢?别急,今天我...
升级小米平板安卓系统,畅享全新... 你有没有发现,你的小米平板用久了,是不是感觉有点卡呢?别急,今天就来教你怎么给它来个系统升级,让它焕...
捷豹安卓系统车载,捷豹安卓系统... 哇,你有没有想过,当你的手机和汽车融为一体,会是怎样的体验呢?想象你正驾驶着你的捷豹,车窗外的风景如...
安卓1到10系统,安卓1.0至... 你有没有想过,手机里的安卓系统就像是我们生活中的好朋友,从青涩的少年成长为稳重的青年呢?从安卓1.0...
安卓8.0停用系统应用,提升使... 你知道吗?最近安卓系统又来了一次大动作,那就是安卓8.0系统开始停用一些系统应用了。这可真是让人有点...
安卓系统修改mtu值,轻松提升... 你有没有想过,你的安卓手机其实是个小小的电脑呢?它里面藏着许多可以自定义的秘密功能,就像修改MTU值...
安卓平板改window系统,探... 你有没有想过,你的安卓平板其实可以摇身一变,变成一个Windows系统的电脑呢?没错,就是那种可以运...
时空猎人安卓苹果系统,探索无尽... 你知道吗?最近在手机游戏圈里,有一款叫做《时空猎人》的游戏可是火得一塌糊涂呢!不管是安卓用户还是苹果...
安卓9.0系统的电视,新一代电... 亲爱的读者们,你是否也像我一样,对科技新玩意儿充满好奇?今天,我要和你聊聊一个让人眼前一亮的话题——...
小pc安装安卓系统,轻松安装安... 你有没有想过,你的小PC也能变身成为安卓系统的超级玩家呢?没错,就是那个平时默默无闻的小家伙,现在也...
高通备份安卓系统,全方位数据安... 你知道吗?在这个科技飞速发展的时代,手机备份可是个不得不提的话题。尤其是对于安卓用户来说,选择一个靠...
谷歌安卓系统有多少,从诞生到全... 你有没有想过,那个无处不在的谷歌安卓系统,究竟在全球有多少用户呢?它就像一个神秘的数字,每天都在悄悄...
fc黄金传说安卓系统,畅享复古... 你有没有听说最近安卓系统上的一款超酷的游戏——《FC黄金传说》?这款游戏可是让不少玩家都沉迷其中,今...
变小的我安卓系统,安卓系统演变... 你有没有发现,最近你的手机好像变轻了?没错,说的就是你,那个陪伴你多年的安卓系统。它悄无声息地进行了...
vivo安卓系统小彩蛋,体验科... 你知道吗?在vivo的安卓系统中,竟然隐藏着一些超有趣的小彩蛋!这些小彩蛋就像是在手机里埋下的宝藏,...
安卓系统如何强制重启,安卓系统... 手机突然卡壳了,是不是又该给它来个“大保健”了?没错,今天就来聊聊安卓系统如何强制重启。别小看这个看...