题解 | #数字在升序数组中出现的次数#
数字在升序数组中出现的次数
http://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2
本题要求空间O(1),时间复杂度O(logn),很容易想到要使用二分查找来做，先找出比k大的下标r，再找出比k小的下标l，最后k有r-l-1个。
public:
int GetNumberOfK(vector<int> data ,int k) {
int n = data.size();
//求比k大的下标
//注意循坏退出条件，当l==r时，若data[mid]<=k，则mid+1为所求，否则为mid（好好理解此时l的取值）
int l=0,r=n-1;
while(l<=r)
{
int mid = (l+r)/2;
if(data[mid] <= k) l=mid+1;
else r=mid-1;
}
int ans = l;
l = 0;r = n-1;
while(l<=r)
{
int mid = (l+r)/2;
if(data[mid] >= k) r=mid-1;
else l=mid+1;
}
ans=ans-r-1;
return ans;
}
};
投递大连飞创信息技术有限公司等公司6个岗位
