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

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

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 暴力出奇迹 lis = [] for i in range(len(nums)): if nums[i] == target: lis.append(i) if lis: return [min(lis),max(lis)] else: return [-1,-1]

下面这个思想就是先用二分找到元素位置，后根据这个位置前后摸索 如果也能找到target那么l和r就变动，但因为有了底下两个while 实际上这个算法也并非严格意义上的O（logn）

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: #设计O（logn）算法 # 先二分定位这个元素的位置 往前往后看看元素一样不一样 # 左闭右开 left,right = 0, len(nums) while left < right: middle = (left + right) // 2 if nums[middle] > target: right = middle # 因为右区间无意义 elif nums[middle] < target: left = middle + 1 else: location = middle break else: return [-1,-1] l,r = location,location # 往前定位 try: # 防止出现越界以及防止-1索引出现 while nums[l-1] == target and (l-1)>=0: l -= 1 # 往后定位 while nums[r+1] == target: r += 1 except: pass return [l,r]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。