方法一：暴力

1.结题思路

暴力法，遍历数组,统计元素出现次数并输出

2.解法

遍历vector数组统计元素出现次数即可

3.具体代码

int GetNumberOfK(vector<int> data ,int k) {
    int cn=0;
    for(vector<int>::iterator it=data.begin();it!=data.end();it++){//遍历并统计元素出现次数
        if(*it==k)cn++;
    } 
    return cn;
}

4.时间复杂度和空间复杂度分析

时间复杂度：O(n)，n为数组元素个数，遍历了一次数组
空间复杂度：O(1)，仅用到了一个整形变量cn

方法一：二分

1.结题思路

因为数据有序，很容易联想到二分查找的前提便是有序，数组中某个值的元素有多少，可用上下界相减计算出来，然后我们想查找元素的上下界，即数组首尾指针的停止移动的位置。

2.解法

• 首先寻找上下界，再用上界-下界+1即得到答案
  当data[mid]<k时，left=mid+1，即left会保持在k第一次出现的位置
  当data[mid]>k时，right=mid-1，即right会保持在k最后一次出现的位置

• 也可直接用STL upper_bound(),upper_bound。
  lower_bound(first,last,val)寻找有序数组或容器的[first,last)范围内第一个值 大于等于 val元素的位置
  upper_bound(first,last,val)寻找有序数组或容器的[first,last)范围内第一个值 大于 val元素的位置

return upper_bound(data.begin(),data.end(),k)-lower_bound(data.begin(),data.end(),k); 

3.图解

4.具体代码

int GetNumberOfK(vector<int> data ,int k) {
    //获取下界，即最终的left 
    int left=0,right=data.size()-1;//数组首末元素 
    while(left<=right){
        int mid=(left+right)/2;
        if(data[mid]<k)left=mid+1;//当data[mid]>=k时不执行，也就是说left会保持在k第一次出现的位置 
        else right=mid-1;
    }
    //获取上界，即最终的right2
    int left2=0,right2=data.size()-1;//数组首末元素 
    while(left2<=right2){
        int mid=(left2+right2)/2;
        if(data[mid]<=k)left2=mid+1;//同理，right2为k最后一次出现的位置 
        else right2=mid-1;    
    }
    return right2-left+1; 
}

5.时间复杂度和空间复杂度分析

时间复杂度：O(logn),二分查找，设问题规模为 n，需要 t 次查找，由二分查找的过程可知，每一次查找问题规模减半，最差情况下，直到问题规模为 1 时才找到或者仍未找到，因此可知：n*(1/2)^t=1则2^t=n，两边取log得t=log2n;
空间复杂度：O(1)，仅用到了两个整形变量