欢迎光临散文网 会员登陆 & 注册

LeetCodeTOP100_34. 在排序数组中查找元素的第一个和最后一个位置

2023-03-13 22:29 作者:方猫zzz  | 我要投稿

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

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


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


你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。


 


示例 1:


输入:nums = [5,7,7,8,8,10], target = 8

输出:[3,4]

示例 2:


输入:nums = [5,7,7,8,8,10], target = 6

输出:[-1,-1]

示例 3:


输入:nums = [], target = 0

输出:[-1,-1]


需要O(nlgn)的时间,想到二分法;

与二分法模板不同的是,实际上是第一个大于等于target的数和第一个大于target的数-1,构成了区间的左右边界;

代码如下:



LeetCodeTOP100_34. 在排序数组中查找元素的第一个和最后一个位置的评论 (共 条)

分享到微博请遵守国家法律