思路:
利用二分查找,分别查找待统计数字的头和尾的下标,最后做差加一即为结果。
C++:
#include <iostream>
#include <vector>
using namespace std; int GetFirstK(vector<int>& nums, int startpos, int endpos, int k)
{
if(startpos > endpos)
return -; int mid = (startpos + endpos) / ; if(nums[mid] == k)
{
if(mid == || (mid > && nums[mid - ] != k))
return mid;
else
endpos = mid - ;
}
else if(nums[mid] < k)
{
startpos = mid + ;
}
else
{
endpos = mid - ;
} return GetFirstK(nums, startpos, endpos, k);
} int GetLastK(vector<int>& nums, int startpos, int endpos, int k)
{
if(startpos > endpos)
return -; int mid = (startpos + endpos) / ;
int lastpos = nums.size() - ; if(nums[mid] == k)
{
if(mid == lastpos || (mid < lastpos && nums[mid + ] != k))
return mid;
else
startpos = mid + ;
}
else if(nums[mid] < k)
{
startpos = mid + ;
}
else
{
endpos = mid - ;
} return GetLastK(nums, startpos, endpos, k);
} int main()
{
int a[] = {, , , , , , , , , };
vector<int> v(a, a +); cout<<GetLastK(v, , , ) - GetFirstK(v, , , ) + <<endl;
}