【剑指offer】数组在排序数组中出现的次数

题目描述

分析：数组有序，采用二分查找无疑

两种方法，时间复杂度差不多，都是利用二分查找，不过统计k出现的次数有所不同而已

方法1：二分查找k，找到任意一个k的下标index，index向两边扩展即可

方法2：二分查找k+0.5和k-0.5的插入位置index1和index2，因为数组元素都是整数，index1-index2就是k出现的次数

时间复杂度:O（log N）

方法1：

int GetNumberOfK(vector<int> v ,int k)
{
    if(v.size()==0)
        return 0;

    //查找任意一个k的位置index
    int low=0;
    int high=v.size()-1;
    int index=-1;
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(v[mid]==k)
        {
            index=mid;
            break;
        }
        else if(v[mid]>k)
        {
            high=mid-1;
        }
        else if(v[mid]<k)
        {
            low=mid+1;
        }
    }
    if(index==-1)
        return 0;

    //index向两边扩展
    int c=0;
    for(int i=index-1; i>=0; i--)
    {
        if(v[i]==k)
            c++;
        else
            break;
    }
    int n=v.size();
    for(int i=index+1; i<n; i++)
    {
        if(v[i]==k)
            c++;
        else
            break;
    }
    return c+1;
}

方法2：

//查找k的插入位置
int f(vector<int> &v,double k)
{
    int low=0;
    int high=v.size()-1;
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(v[mid]>k)
        {
            high=mid-1;
        }else if(v[mid]<k)
        {
            low=mid+1;
        }
    }
    return low;
}
int GetNumberOfK(vector<int> v ,int k)
{
    if(v.size()==0)
        return 0;
    int x=f(v,k+0.5);
    int y=f(v,k-0.5);
    if(x==-1||y==-1)
        return 0;
    //k+0.5和k+0.5的插入位置相减就是k出现次数
    return x-y;
}