您的位置:首页 > 财经 > 金融 > 【在排序数组中查找元素的第一个和最后一个位置】python刷题记录

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

2024/12/23 9:29:16 来源:https://blog.csdn.net/m0_73629042/article/details/140724734  浏览:    关键词:【在排序数组中查找元素的第一个和最后一个位置】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]=1else:dict[num]+=1if not dict[target]:return [-1,-1]#当前遍历数字次数dict1=defaultdict(list)first=0for i in range(n):if nums[i]==target:if not dict1[target]:first=idict1[target]=1else:dict1[target]+=1if 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=0right=len(nums)-1while left<=right:mid=(left+right)//2if nums[mid]<target:left=mid+1 #[mid+1,right]else:right=mid-1 #[left,mid-1]return leftstart=bi_find(nums,target)if start==len(nums) or nums[start]!=target:return [-1,-1]#巧妙在这里end的设置,下一个数的前一个就是end=bi_find(nums,target+1)-1return [start,end]

哈哈哈,差不多() 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com