题目：

统计一个数字在排序数组中出现的次数。

思路：

1、顺序遍历

顺序扫描一遍数组，统计该数字出现的次数。

时间复杂度：O(n)

2、二分查找

假设我们需要找的数字是k，那么就需要找到数组中的第一个k和最后一个k出现的位置。

如何通过二分查找得到第一个k的位置呢？

取数组中间的数字与k作比较，

如果该数字比k大，那么k只能出现在前半部分，那么下一轮只能在前半部分找；

如果该数字比k小，那么k只能出现在后半部分，那么下一轮只能在后半部分找；

如果该数字等于k，需要判断这是不是第一个k，如果该数字的前一个数字不是k，那么该数字就是第一个k，否则需要在前半部分继续寻找第一个k；

寻找最后一个k的方法与寻找第一个k的方法一样。

代码：

#include <iostream>

using namespace std;

int getFirstK(int* data,int k,int start,int end){

    while(start<=end){

        int mid=start+((end-start)>>1);

        if(data[mid]==k){

            if((mid>0 && data[mid-1]!=k) || mid==0)

                return mid;

            else

                end=mid-1;

        }

        else if(data[mid]>k)

            end=mid-1;

        else

            start=mid+1;

    }

    return -1;

}

int getLastK(int* data,int length,int k,int start,int end){

    while(start<=end){

        int mid=start+((end-start)>>1);

        if(data[mid]==k){

            if((mid<length-1 && data[mid+1]!=k) || mid==length-1)

                return mid;

            else

                start=mid+1;

        }

        else if(data[mid]<k)

            start=mid+1;

        else

            end=mid-1;

    }

    return -1;

}

int getNumberOfK(int* data,int length,int k){

    if(data==NULL || length<=0)

        return 0;

    int first=getFirstK(data,k,0,length-1);

    int last=getLastK(data,length,k,0,length-1);

    cout<<first<<" "<<last<<endl;

    if(first!=-1 && last!=-1)

        return last-first+1;

    return 0;

}

int main()

{

    int A[]={1,2,3,3,3,3,4,5};

    int len=sizeof(A)/sizeof(A[0]);

    int k=3;

    cout << getNumberOfK(A,len,k) << endl;

    return 0;

}

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/70610bf967994b22bb1c26f9ae901fa2?rp=2

AC代码：

class Solution {

public:

    int GetNumberOfK(vector<int> data,int k) {

        int len=data.size();

        if(len<=0)

            return 0;

        int first=getFirstK(data,k,0,len-1);

        int last=getLastK(data,len,k,0,len-1);

        if(first!=-1 && last!=-1)

            return last-first+1;

        return 0;

    }

    int getFirstK(const vector<int> &data,int k,int start,int end){

        int mid;

        while(start<=end){

            mid=start+((end-start)>>1);

            if(data[mid]==k){

                if((mid>0 && data[mid-1]!=k) || mid==0)

                    return mid;

                else

                    end=mid-1;

            }

            else if(data[mid]>k)

                end=mid-1;

            else

                start=mid+1;

        }

        return -1;

    }

    int getLastK(const vector<int> &data,int length,int k,int start,int end){

        int mid;

        while(start<=end){

            mid=start+((end-start)>>1);

            if(data[mid]==k){

                if((mid<length-1 && data[mid+1]!=k) || mid==length-1)

                    return mid;

                else

                    start=mid+1;

            }

            else if(data[mid]>k)

                end=mid-1;

            else

                start=mid+1;

        }

        return -1;

    }

};

巴特西

（剑指Offer）面试题38：数字在排序数组中出现的次数

题目：

思路：

代码：

在线测试OJ：

最新文章

热门文章