[LeetCode] Search for a Range
來源：程序員人生 發布時間：2015-07-24 09:27:01 閱讀次數：3915次
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,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
解題思路：
這道題的題意是找到排序數組中目標值的下標范圍，這個數組可能會有相同的元素。
題目要求時間復雜度在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;
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
