[编程题]数字在排序数组中出现的次数
样例 8
1 2 3 3 3 3 4 5 3
链接：https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2?orderByHotValue=1&page=8&onlyReference=false
来源：牛客网
class Solution {
public:
int erfen(vector<int>data,double k){
int l = 0;
int r = data.size()-1;
while(l<=r){
int mid = (l+r)/2;
if(data[mid]<k)l = mid+1;
else r = mid-1;
}
return l;
}
int GetNumberOfK(vector<int> data ,int k) {
int p1 = erfen(data,k+0.5);
int p2 = erfen(data,k-0.5);
// cout<<p1-p2<<endl;
return p1-p2;
}
};#include<bits/stdc++.h>
using namespace std;
vector<int>vc;
class Solution {
public:
int erfen_first(vector<int> data ,int l,int r,double k){
if(l>=r){
if(data[l]==k)return l;
else return -1;
}
int mid = (l+r)/2;
if(data[mid]<k)return erfen_first(data,mid+1,r,k);
else return erfen_first(data,l,mid,k);
}
// 1 2 3 3 4 5
int erfen_last(vector<int> data ,int l,int r,double k){
if(l>=r){
if(data[l]==k)return l;
if(data[l-1]==k)return l-1;
else return -1;
}
int mid = (l+r)/2;
if(data[mid]<=k)return erfen_last(data,mid+1,r,k);
else return erfen_last(data,l,mid,k);
}
//1 2 3 3 3 4 5
int GetNumberOfK(vector<int> data ,int k) {
auto pp = equal_range(data.begin(),data.end(),k);
return pp.second-pp.first;
int len = data.size();
if(len==0)return 0;
int pos = erfen_first(data,0,len-1,k);
if(pos!=-1)
{
int pos2 = erfen_last(data,0,len-1,k);
// cout<<pos<<" "<<pos2<<endl;
return pos2-pos+1;
}
else return 0;
}
};
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int num;
cin>>num;
vc.push_back(num);
}
int k;
cin>>k;
Solution ss;
int an = ss.GetNumberOfK(vc,k);
cout<<an<<endl;
return 0;
}