LeetCode算法|笔记:第34题:(题目好长)

2020年10月13日 22:26:48 拜伦建站 149次

  题目:在排序数组中查找元素的第一个和最后一个位置

  题目:在排序数组中查找元素的第一个和最后一个位置

  题目:在排序数组中查找元素的第一个和最后一个位置

  本文答案参考自 LeetCode 官方题解。

  题目描述

  给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

  你的算法时间复杂度必须是 O(log n) 级别。

  如果数组中不存在目标值,返回 [-1, -1]。

  又是 O(log n) 级别的时间复杂度,

  那就又 自然而然 地想到了 二分查找。

  二分查找 找一个还好,

  那要是找两个,而且还是左右两边的两个,那就有点麻烦了

  所以这道题的难度得是 中等 ╰( ̄▽ ̄)╭

  【方法1】二分查找

  跟普通的二分查找不同的是:

  找到的元素不一定是最左边(或最右边)的元素

  所以当找到一个元素时,还要继续向左(或向右)查找

  为实现此目标,我们需要用一个 flag 来标记 是向左还是向右查找

  查找最左边元素的代码逻辑:

  将 flag 记为向左

  使用二分查找,

  当元素在左边时,当然是向左继续二分啦

  当元素在右边时,当然是向右继续二分啦

  而当找到元素时,向左继续二分查找

  如此进行,直到左边指针和右边指针重合

  查找最右边元素的代码逻辑:

  将 flag 记为向右

  使用二分查找,

  当元素在左边时,当然是向左继续二分啦

  当元素在右边时,当然是向右继续二分啦

  而当找到元素时,向右继续二分查找

  如此进行,直到左边指针和右边指针重合

  贴代码(以后我都会贴代码的 (* ̄ω ̄)

  

LeetCode算法|笔记:第34题:(题目好长)

上一篇:聚好看:小猪佩奇霸榜AI语音搜索 后浪主导家庭大屏点播权
下一篇:鸿翔东辰名邸位置解析优点跟缺点

声明:本页内容由好推网络科技有限公司通过网络收集编辑所得,所有资料仅供用户参考;本站不拥有所有权,也不承认相关法律责任。如您认为本网页中有涉嫌抄写的内容,请及时与我们联系进行举报,并提供相关证据,工作人员会在5个工作日内联系您,一经查实,本站将立刻删除涉嫌侵权内容。

相关资讯 Releva ntnews
  1. 我们的承诺
  2. 我们的实力
  3. 我们的未来

站点地图

Copyright © 2002-2019 拜伦建站 sh-bilon.com 版权所有