题解 | #数字在升序数组中出现的次数#

题意思路：
统计一个数字在升序数组中出现的次数。

方法一:暴力枚举
题意很简单，寻找一个数字的出现次数，一个朴素的想法就是暴力一边数组中这个数字的出现次数

复杂度分析

时间复杂度：O(N)，N数组的长度，遍历数组；

空间复杂度：O(1)，未开辟新空间.

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int res=0;
       for(int i:data){//遍历数组
           if(i==k)res++;//统计k的出现次数
       }
        return res;
    }
};

方法二：二分查找
给定数组是升序的，可以发现满足二分的性质：

即可以使用两个指针不断根据升序的数组从小到大的性质寻找数字k在数组中下界和上界的位置，

从而求出数字在升序数组中出现的次数。

图解：

复杂度分析

时间复杂度：O(logN)，N数组的长度，二分遍历数组的时间复杂度为logN；

空间复杂度：O(1)，未开辟新空间。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
       int l=0,r=data.size()-1;//两个指针分别指向数组开头和结尾
        int low,up;
        if(!data.size())return 0;//记得特判数组长度为空
        while(l<r){//当指针l小于指针r满足二分条件
            int mid=l+r>>1;//得到两个指针之间的中点
            if(data[mid]>=k){//如果中点值大于等于k
                r=mid;//说明k在l到mid区间，所以r=mid；
            }
            else l=mid+1;//否则中点值小于k 说明k在mid+1到r区间，所以l=mid+1；
        }
        if(data[l]!=k)return 0;//如果数组中没有k则返回为0
        low=l;//记录得到的下界
        l=0,r=data.size()-1;
        while(l<r){//当指针l小于指针r满足二分条件
            int mid=l+r+1>>1;//得到两个指针之间的中点
            if(data[mid]<=k){//如果中点值小于等于k
                l=mid;//说明k在mid到r区间，所以l=mid；
            }
            else r=mid-1;//否则中点值大于k 说明k在l到mid-1区间，所以r=mid-1；
        }
        up=l;//记录得到的上界界
        return up-low+1;//统计上下界之间个数
    }
};