给定一个以非降序排序的整数nums数组,查找给定目标值的开始和结束位置。
如果在数组中找不到目标,则返回[-1,-1]。
你必须编写一个运行时复杂度为O(log n)的算法。
我用leetcode写了这段代码,但它只通过了88个测试用例中的67个。有人能告诉我这段代码的问题吗?
class Solution {
public:
int FirstOccurence(vector<int> arr, int n, int x) {
int low = 0, high = n - 1;
int ans = -1;
while (low <= high) {
int mid = (low + high) / 2;
// maybe an answer
if (arr[mid] == x) {
ans=mid;
high=mid-1;
}
else if (arr[mid]< x) {
low=mid+1;
}
else high=mid-1;
}
return ans;
}
int LastOccurence(vector<int> arr, int n, int x) {
int low = 0, high = n - 1;
int ans = -1;
while (low <= high) {
int mid = (low + high) / 2;
// maybe an answer
if (arr[mid]== x) {
ans = mid;
//look for smaller index on the left
low=mid+1;
}
else if(arr[mid]>x){
high=mid-1;
}
else {
low = mid + 1; // look on the right
}
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
int n=nums.size()-1;
int k=target;
int a=FirstOccurence(nums,n,k);
int b=LastOccurence(nums,n,k);
return{a,b};
}
};
字符串
1条答案
按热度按时间bbuxkriu1#
您将
nums.size() - 1
发送到二进制搜索函数,并在其中生成high = n - 1
,实际上生成high = nums.size() - 2
,因此所有target
是vector
中最大数字的测试都将失败。一个简单的解决方法是根本不发送
n
。您已经发送了vector
,并且可以在函数内部调用.size()
:个字符
然后在呼叫现场:
型
另一种方法是使用标准库中的
std::equal_range
:型