专业网站开发/亚马逊查关键词搜索量的工具

剑指offer：面试题38——数字在排序数组中出现的次数

题目：

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

思路：如{1,2,3,3,3,3,4,5}

可以采用二分法，分别找到对应的数字的开头第一个和最后一个

class Solution {
public:
int GetNumberFirst(vector<int> data,int begin,int end,int k)
{if(begin>end) return -1;int size=data.size();int mid=(begin+end)/2;if(data[mid]>k)end=mid-1;else if(data[mid]<k)begin=mid+1;else{//如果data[mid]==k且它前一个不是k，说明mid是第一个值为k的数if( (mid>0 && data[mid-1]!=k)||mid==0)return mid;elseend=mid-1;}return GetNumberFirst(data,begin,end,k);
}int GetNumberLast(vector<int> data,int begin,int end,int k)
{if(begin>end) return -1;   //begin>end，则返回-1说明没找到int size=data.size();int mid=(begin+end)/2;if(data[mid]>k) end=mid-1;else if(data[mid]<k) begin=mid+1;else{//如果data[mid]==k且它后一个不是k，说明mid是最后一个值为k的数if( (mid<size-1&&data[mid+1]!=k)||mid==size-1)return mid;else begin=begin+1;}return GetNumberLast(data,begin,end,k);
}
public:int GetNumberOfK(vector<int> data ,int k) {int size=data.size();if(size<=0)return 0;int begin=0;int end=size-1;int retB=0;int retE=0;retB=GetNumberFirst(data,begin,end,k);retE=GetNumberLast(data,begin,end,k);if(retB==-1||retE==-1)return 0;else if(retB==retE && data[retB]==k ) return 1;else return retE-retB+1;}
};