【在排序数组中查找元素的第一个和最后一个位置】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]

哈哈哈，差不多（）