【牛客题霸题解】数字在升序数组中出现的次数

这道题目直接遍历一遍也是可以得到答案的。不过如果想快一点的话我们可以用二分查找

前置题目：NC105 二分查找
用二分的方法找到第一个大于等于k的位置(lower_bound)和第一个大于k的位置(upper_bound)，然后相减就可以得到答案了。
如下图：lower_bound = 2,upper_bound = 6 所以3出现的次数为6-2=4次。

c++

class Solution {
public:
    int lower_bound(vector<int> data,int k)
    {
        int left = 0;
        int right = data.size();
        while(left<right)
        {
            int mid = (left+right)/2;
            if(data[mid] >= k)//后面的都可以不要了
            {
                right = mid; 
            }
            else{//前面的都不要了
                left = mid+1;
            }
        }
        return right;
    }
    int upper_bound(vector<int> data,int k)
    {
        int left = 0;
        int right = data.size();
        while(left<right)
        {
            int mid = (left+right)/2;
            if(data[mid] > k)//后面的都可以不要了
            {
                right = mid;  
            }
            else{//前面的都不要了
                left = mid+1;
            }
        }
        return right;
        return 0;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        return upper_bound(data,k)-lower_bound(data,k);

    }
};

java

public class Solution {
    public int lower_bound(int[] data,int k)
    {
        int left = 0;
        int right = data.length;
        while(left<right)
        {
            int mid = (left+right)/2;
            if(data[mid] >= k)//后面的都可以不要了
            {
                right = mid;
            }
            else{//前面的都不要了
                left = mid+1;
            }
        }
        return right;
    }
    int upper_bound(int[] data,int k)
    {
        int left = 0;
        int right = data.length;
        while(left<right)
        {
            int mid = (left+right)/2;
            if(data[mid] > k)//后面的都可以不要了
            {
                right = mid; 
            }
            else{//前面的都不要了
                left = mid+1;
            }
        }
        return right;

    }
    public int GetNumberOfK(int [] array , int k) {
        return upper_bound(array,k)-lower_bound(array,k);
    }
}

python

class Solution:
    def GetNumberOfK(self, data, k):
        def upper_bound(data,k):
            left = 0
            right = len(data)
            while left<right:
                mid = int((left+right)/2)
                if data[mid] > k:
                    right = midjavascript:void(0);
                else:
                    left = mid+1
            return right
        def lower_bound(data,k):
            left = 0
            right = len(data)
            while left<right:
                mid = int((left+right)/2)
                if data[mid] >= k:
                    right = mid
                else:
                    left = mid+1
            return right
        return upper_bound(data,k)-lower_bound(data,k);