[LeetCode] Search for a Range
发布时间：2020-12-13 20:45:44 所属栏目：PHP教程 来源：网络整理
导读：Search for a Range 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 [⑴,
|
Search for a Range 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
For example, 解题思路： 这道题的题意是找到排序数组中目标值的下标范围，这个数组可能会有相同的元素。 题目要求时间复杂度在O(logn)。3次2分查找。第1次找到1个值为target的下标k，第2次找到0~k中值为target的最小下标，第3次找到k~len⑴中值为target的最大下标。每次的时间复杂度为O（logn）。 class Solution {
public:
vector<int> searchRange(vector<int>& nums,int target) {
vector<int> result({⑴,⑴});
int start=0,end=nums.size()⑴;
int middle;
//找到第1个
while(start<=end){
middle=(start+end)/2;
if(nums[middle]==target){
result[0]=result[1]=middle;
break;
}else if(nums[middle]>target){
end=middle⑴;
}else{
start=middle+1;
}
}
if(result[0]!=⑴){
//找到最小的那个下标
start=0;
end=result[0]⑴;
while(start<=end){
middle=(start+end)/2;
if(nums[middle]==target){
end=middle⑴;
result[0]=middle;
}else{
start=middle+1;
}
}
//找到最大的那个下标
start=result[1]+1;
end=nums.size()⑴;
while(start<=end){
middle=(start+end)/2;
if(nums[middle]==target){
start=middle+1;
result[1]=middle;
}else{
end=middle⑴;
}
}
}
return result;
}
}; （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |