当前位置 博文首页 > dastu的博客:在排序数组中查找元素的第一个和最后一个位置 (pyt
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是?O(log n) 级别。
如果数组中不存在目标值,返回?[-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
?
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1,-1]
l=0
r=len(nums)-1
while l<=r:
mid=(l+r)//2
if nums[mid]==target:
temp=mid
while temp>0 and nums[temp-1]==target:
temp-=1
while mid<len(nums)-1 and nums[mid+1]==target:
mid+=1
return [temp,mid]
elif nums[mid]<target and mid<r:
l=mid+1
elif nums[mid]>target and mid>l:
r=mid-1
else:
return [-1,-1]
?
cs