面试题38:数字在排序数组中出现的次数

题目:统计一个数字在排序数组中出现的次数。例如输入数组{1,2,3,3,3,3,4,5}和数字3,由于3在数组中出现了4次,因此输出4.


分析

看到排序数组,我们自然而然会想到二分法。但平常的二分法只能找到这个数字,并不能找出出现的次数,或者该数字的最左和最右边界。那么我们就需要改进一下:

假设数组是升序排列的,当我们用二分法找到这个数时,再继续用二分法去找它的左右边界,因此需要分别写两个函数。以找左边界为例,设现在有left,right和mid分别指向数组的最左,最右和中间数字,且中间数字恰好为我们要找的数字。这时候就在left和mid之间用二分法去找,假设mid2=left+(mid-left)/2;此时有如下几种情况:

综上,我们可以利用递归去找最左和最右的数字,将其下标相减就可以得到该数字出现的次数。

代码如下:

int _GetLeft(const vector<T>&amp; v,int left,int right,const T&amp; k)
{
    if(left==right)
        return right;
    int mid=left+(right-left)/2;
    if(v[mid]==k)
        return _GetLeft(v,left,mid,k);
    else
        return _GetLeft(v,mid+1,right,k);
}

template<typename T>
int _GetRight(const vector<T>&amp; v,int left,int right,const T&amp; k)
{
    if(left==right)
        return left;
    if(left==right-1)
    {
        if(v[left]==k)
            return left;
        else
            return right;
    }
    int mid=left+(right-left)/2;
    if(v[mid]==k)
        return _GetRight(v,mid,right,k);
    else
        return _GetRight(v,left,mid-1,k);
}

template<typename T>
int _NumberOfK(const vector<T>&amp; v,int left,int right,const T&amp; k)
{
    if(left>right)
        return 0;
    int mid=left+(right-left)/2;
    if(v[mid]>k)
        return _NumberOfK(v,left,mid-1,k);
    else if(v[mid]<k)
        return _NumberOfK(v,mid+1,right,k);
    else
    {
        int r=_GetRight(v,mid,right,k);
        int l=_GetLeft(v,left,mid,k);
        //cout<<l<<" "<<r<<endl;
        return r-l+1;
    }
}

template<typename T>
int NumberOfK(const vector<T>&amp; v,const T&amp; k)
{
    return _NumberOfK(v,0,v.size()-1,k);
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")