信息类网站怎么做厦门网站设计公司
Problem: 34. 在排序数组中查找元素的第一个和最后一个位置
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
二分查找,
口诀:左右右,求左段区间的右端点,动r
解题方法
两次二分查找
复杂度
时间复杂度: O ( l o g n ) O(logn) O(logn) 二次两份查找
空间复杂度: O ( 1 ) O(1) O(1) 若干中间变量
Code
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if not nums: return [-1, -1]n = len(nums)l, r = 0, n - 1res = [-1, -1]# 确定左区间while l < r:mid = l + r >> 1if nums[mid] >= target:r = midelse:l = mid + 1if nums[l] == target:res[0] = l# 确定右区间r = n - 1while l < r:mid = l + r + 1>> 1if nums[mid] <= target:l = midelse:r = mid - 1if nums[l] == target: res[1] = rreturn res