【刷题日记】34. 在排序数组中查找元素的第一个和最后一个位置

简介: 本次刷题日记的第 72 篇,力扣题为:34. 在排序数组中查找元素的第一个和最后一个位置 ,中等

本次刷题日记的第 72 篇,力扣题为:34. 在排序数组中查找元素的第一个和最后一个位置,中等

一、题目描述:

image.png

今天回来加点紧,写一个随机中等题练练手,34. 在排序数组中查找元素的第一个和最后一个位置,看看需要我们咋找


二、这道题考察了什么思想?你的思路是什么?

  1. 在排序数组中查找元素的第一个和最后一个位置 给了我们哪些有用的信息:
  • 题目给出一个数组,是有序的,且是升序的,元素是整型的数字,题目给出一个 target ,要求我们找到 target 对应到数组中的开始位置和结束位置,这里指的是数组索引的位置
  • 题目要求我们时间复杂度是 O(nlogn)
  • 当然,题目给出的数组中,并不一定存在给出的 target 值,如果不存在,则返回 [-1,-1]

分析

其实看到这道题,有一点我们就能够非常明确了,那就是题目给出的数组是升序的,另外题目要求我们做的一件事情是去做查找

稍加一想,我们就应该要考虑,这个题是不是要用 二分法来进行处理,是否合适

其实我们拿到题,最无脑的就是遍历一遍数组,记录下 target 出现的第一个位置和最后一个位置,输出结果即可,但是,题目有时间复杂度的要求,咱不能这么干

那么二分法使用啥情况呢?

  • 适用于对于有序的一串数字中高效的查找某一个数字

那么应对到咱们这个题可以知道,我们是要找 1 个数字的最开始位置和最尾巴位置,那么找第一个数字的时候从头开始找?最后一个位置的时候,从尾巴开始找?说起来咋有点像是双指针

不过我们可以这样来做,同样是无脑的使用二分法做查找,思考一下,我们是不是可以从左到右找 target ,找到 target 就是第一个位置

那么 target 的最后一个位置,我们可以是找比 target 大的数字就可以了,找到之后,索引减去 1 ,就是 target 的最后一个位置了

image.png

那么对应到 golang 中,我们可以使用一下库函数,库函数用起来总比咱们的手撸代码效率高吧

咱们可以使用 golang 中 sort 库的 SearchInts 函数

SearchInts 在排序的整数切片中搜索 x 并返回 Search 指定的索引。, 如果 x 不存在,则返回值是插入 x 的索引

三、编码

根据上述逻辑和分析,我们就可以翻译成如下代码

  • 我们可以自己写二分,也可以使用库函数,不过我们可以感受一个库函数带给我们的高效,兄弟们可以尝试一下自己写二分法,和使用库做出的题,效率分别都是咋样的

编码如下:

func searchRange(nums []int, target int) []int {
   left := sort.SearchInts(nums, target)
    if left == len(nums) || nums[left] != target {
        return []int{-1, -1}
    }
    right := sort.SearchInts(nums, target + 1) - 1
    return []int{left, right}
}

四、总结:

image.png

时间复杂度没的说,题目就是要求我们时间复杂度保持 O(nlogn)

空间复杂度这里比较明确,我们就引入了一些常数级别的变量,因此空间复杂度为 O(1)

原题地址:34. 在排序数组中查找元素的第一个和最后一个位置

今天就到这里,学习所得,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

image.png

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~



相关文章
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法 索引 Python
【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
解决LeetCode "在排序数组中查找元素的第一个和最后一个位置" 问题的方法。第一种方法是使用两次二分查找,首先找到目标值的最左边界,然后找到最右边界。第二种方法是利用Python的list.index()方法,先正序找到起始位置,再逆序找到结束位置,并给出了两种方法的Python实现代码。
61 0
|
6月前
|
算法
leetcode-34:在排序数组中查找元素的第一个和最后一个位置
leetcode-34:在排序数组中查找元素的第一个和最后一个位置
33 0
|
算法
【算法挨揍日记】day10——704. 二分查找、34. 在排序数组中查找元素的第一个和最后一个位置
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
363 0
LeetCode-34 在排序数组中查找元素的第一个和最后一个位置
LeetCode-34 在排序数组中查找元素的第一个和最后一个位置
|
索引
力扣34在排序数组中查找元素的第一个和最后一个位置:思路分析+图文详解+代码实现(最靠左索引,最靠右索引)
力扣34在排序数组中查找元素的第一个和最后一个位置:思路分析+图文详解+代码实现(最靠左索引,最靠右索引)
57 0
|
算法
每日一题—— 在排序数组中查找元素的第一个和最后一个位置
每日一题—— 在排序数组中查找元素的第一个和最后一个位置
|
存储 算法 测试技术
LeetCode算法小抄--O(1)时间下删除-查找数组中任意元素
LeetCode算法小抄--O(1)时间下删除-查找数组中任意元素
|
算法
力扣34题. 在排序数组中查找元素的第一个和最后一个位置
力扣34题. 在排序数组中查找元素的第一个和最后一个位置
84 0
|
算法
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
108 0
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置