【在排序数组中查找元素的第一个和最后一个位置】python刷题记录
R2-分治
有点easy的感觉,感觉能用哈希表
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
n=len(nums)
dict=defaultdict(list)
#初始赋值哈希表,记录出现次数
for num in nums:
if not dict[num]:
dict[num]=1
else:
dict[num]+=1
if not dict[target]:
return [-1,-1]
#当前遍历数字次数
dict1=defaultdict(list)
first=0
for i in range(n):
if nums[i]==target:
if not dict1[target]:
first=i
dict1[target]=1
else:
dict1[target]+=1
if dict1[target]==dict[target]:
return [first,i]
很憋屈地过了,用了2个哈希表,感觉好浪费。
等等,这好像是二分查找问题。(因为这是个排序数组,然后如果有相同元素一定是相邻的。。。。。)
灵神有3种写法 闭区间、左闭右开区间和开区间三种写法
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def bi_find(nums:List[int],target:int)->int:
#闭区间版的二分查找
left=0
right=len(nums)-1
while left<=right:
mid=(left+right)//2
if nums[mid]<target:
left=mid+1 #[mid+1,right]
else:
right=mid-1 #[left,mid-1]
return left
start=bi_find(nums,target)
if start==len(nums) or nums[start]!=target:
return [-1,-1]
#巧妙在这里end的设置,下一个数的前一个就是
end=bi_find(nums,target+1)-1
return [start,end]
哈哈哈,差不多()
原文地址:https://blog.csdn.net/m0_73629042/article/details/140724734
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!