数字在排序数组中出现的次数

题目描述

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

 

 

 

 

提交链接：点击

 

 

 

 

思路：

 　　方法一：遍历一次数据即可，时间复杂度O(n)。

  　　方法二：由于数组有序，采用二分查找。

 

 

代码：

//方法一
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int count=0;
        for(int i=0;i<data.size();i++){
            if(k==data[i]){
                count++;
            }
        }
        return count;
    }
};

//方法二
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //二分查找 找一个数字的起始位置和终止位置，相减即可
        int low=lower(data,k);
        int high=upper(data,k);
        return high-low+1;
    }
    int lower(vector<int> data, int k){
        int low=0,high=data.size()-1;
        int mid;
        while(low<=high){
            mid=(low+high)/2;
            if(data[mid]<k){
                low=mid+1;
            }else{
                high=mid-1;
            }
        }
        return low;
    }
    int upper(vector<int> data, int k){
        int low=0,high=data.size()-1;
        int mid;
        while(low<=high){
            mid=(low+high)/2;
            if(data[mid]<=k){
                low=mid+1;
            }else{
                high=mid-1;
            }
        }
        return high;
    }
};