leetcode 【 Search for a Range 】python 实现
2024-08-23 08:47:38
题目:
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1]
.
For example,
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.
代码:oj测试通过 Runtime: 91 ms
class Solution:
# @param A, a list of integers
# @param target, an integer to be searched
# @return a list of length 2, [index1, index2]
def searchAllTarget(self, A, index, target):
# left index
left_index = index
curr_index = index
while curr_index>=0 and A[curr_index]==target:
left_index = curr_index
curr_index = curr_index-1
# right index
right_index = index
curr_index = index
while curr_index<len(A) and A[curr_index]==target:
right_index = curr_index
curr_index = curr_index+1
return [left_index,right_index] def searchRange(self, A, target):
# none case
if A is None:
return None
# short length cases
if len(A)==1 :
return[[-1,-1],[0,0]][A[0]==target]
# binary search
start = 0
end = len(A)-1
while start<=end :
if start==end:
if A[start]==target :
return self.searchAllTarget(A, start, target)
else :
return [-1,-1]
if start+1==end :
if A[start]==target :
return self.searchAllTarget(A, start, target)
elif A[end]==target :
return self.searchAllTarget(A, end, target)
else :
return [-1,-1]
mid = (start+end)/2
if A[mid]==target :
return self.searchAllTarget(A, mid, target)
elif A[mid]>target :
end = mid-1
else :
start = mid+1
思路:
这道题还是基于binary search,但是要求找到的是某个值的range。
分两步完成:
step1. 常规二分查找到target的某个index;如果没有找到则返回[-1,-1]
step2. 假设A中可能有多个位置为target,则从step1找到的index开始向左右search,直到把index左右两侧的target都找出来。
齐活儿
最新文章
- msdia80.dll文件出现在磁盘根目录下的解决方案
- jsp 中登录验证 注销 的模版
- 转:WCF、WebAPI、WCFREST、WebService之间的区别
- 第七课第三节,T语言流程语句(版本5.0)
- 养成好的JAVA编码习惯
- Windows7:Visual Studio 2008试用版的评估期已经结束解决方法
- static_cast、const_cast和reinterpret_cast学习
- python单元测试之unittest
- NSURLSessionDownloadTask 下载文件
- 最长回文(Manacher)
- jsp的标签库和自定义标签
- BZOJ第1页养成计划
- Codeforces 1065F(树形dp)
- 我的WafBypass之道(SQL注入篇)
- Atcoder Tenka1 Programmer Contest 2019 E - Polynomial Divisors
- .Net Core命令行配置-配置介绍
- jQuery change事件
- tf入门-卷积步长strides参数的具体解释
- python格式化输出、逻辑表达式和字符编码
- [转]Javascript 取小数点后面N位