本次刷题日记的第 72 篇,力扣题为:34. 在排序数组中查找元素的第一个和最后一个位置,中等
一、题目描述:
今天回来加点紧,写一个随机中等题练练手,34. 在排序数组中查找元素的第一个和最后一个位置,看看需要我们咋找
二、这道题考察了什么思想?你的思路是什么?
- 在排序数组中查找元素的第一个和最后一个位置 给了我们哪些有用的信息:
- 题目给出一个数组,是有序的,且是升序的,元素是整型的数字,题目给出一个 target ,要求我们找到 target 对应到数组中的开始位置和结束位置,这里指的是数组索引的位置
- 题目要求我们时间复杂度是 O(nlogn)
- 当然,题目给出的数组中,并不一定存在给出的 target 值,如果不存在,则返回 [-1,-1]
分析
其实看到这道题,有一点我们就能够非常明确了,那就是题目给出的数组是升序的,另外题目要求我们做的一件事情是去做查找
稍加一想,我们就应该要考虑,这个题是不是要用 二分法来进行处理,是否合适
其实我们拿到题,最无脑的就是遍历一遍数组,记录下 target 出现的第一个位置和最后一个位置,输出结果即可,但是,题目有时间复杂度的要求,咱不能这么干
那么二分法使用啥情况呢?
- 适用于对于有序的一串数字中高效的查找某一个数字
那么应对到咱们这个题可以知道,我们是要找 1 个数字的最开始位置和最尾巴位置,那么找第一个数字的时候从头开始找?最后一个位置的时候,从尾巴开始找?说起来咋有点像是双指针
不过我们可以这样来做,同样是无脑的使用二分法做查找,思考一下,我们是不是可以从左到右找 target ,找到 target 就是第一个位置
那么 target 的最后一个位置,我们可以是找比 target 大的数字就可以了,找到之后,索引减去 1 ,就是 target 的最后一个位置了
那么对应到 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} }
四、总结:
时间复杂度没的说,题目就是要求我们时间复杂度保持 O(nlogn)
空间复杂度这里比较明确,我们就引入了一些常数级别的变量,因此空间复杂度为 O(1)
原题地址:34. 在排序数组中查找元素的第一个和最后一个位置
今天就到这里,学习所得,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~