数字在排序数组中出现的次数

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

分析:直接方法,顺序扫描数组得到出现次数。时间复杂度为O(n)。更快的方法,由于数组有序,可以用二分法得到第一个3和最后一个3的位置,就确定了出现多少次。时间复杂度为O(logn)

实现:

int GetFirstK(int* data,int length,int k,int start,int end)  //得到第一个k的位置
{
    if(start>end)
        return -1;
        
    int middleIndex=(start+end)/2;
    int middleData=data[middleIndex];
    
    if(middleData==k)
    {
        if((middleIndex>0&&data[middleIndex-1]!=k)||middleIndex==0)
            return middleIndex;
        else
            end=middleIndex-1;
    }
    else if(middleData>k)
        end=middleIndex-1;
    else
        start=middleIndex+1;
    
    return GetFirstK(data,length,k,start,end);
}

int GetLastK(int* data,int length,int k,int start,int end)  //得到最后一个k的位置
{
    if(start>end)
        return -1;
        
    int middleIndex=(start+end)/2;
    int middleData=data[middleIndex];
    
    if(middleData==k)
    {
        if((middleIndex<length-10&&data[middleIndex+1]!=k)||middleIndex==length-1)
            return middleIndex;
        else
            start=middleIndex+1;
    }
    else if(middleData<k)
        start=middleIndex+1;
    else
        end=middleIndex-1;
    
    return GetLastK(data,length,k,start,end);
}

int GetNumberOfK(int* data,int length,int k)
{
    int number=0;
    if(data!=NULL&&length>0)
    {
        int first=GetFirstK(data,length,k,0,length-1);
        int last=GetLastK(data,length,k,0,length-1);
        
        if(first>-1&&last>-1)
            number=last-first+1;
    }
    return number;
}


本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1587763

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。