一、题目描述

JZ37数字在升序数组中出现的次数
题目大意：找到指定数字在升序数组中出现的次数
注意审题：升序数组

二、算法1（暴力遍历）

算法思路

1.总体思路：直接遍历一次数组,当遇到指定数字时计数即可
2.这种方法虽然直观,但是并没有用上题目中提供的升序这一信息,因此一般不是最优解

代码实现（C++11）

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int ans = 0;
        for(auto & d : data) ans += d == k;
        return ans;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

三、算法2（二分法）

算法思路

1.总体思路：由于题目给出的数组是升序的,因此我们可以联系到一种高效的查找算法--二分法
2.对于一段出现在数组中的指定数字,我们只要确定的它出现的第一个位置的下标l,和最后一个位置的下标r,即可得到它的长度为r - l + 1
3.实现细节：需要理解两种常用的二分模板,求大于等于x的第一个数的位置和求小于等于x的第一个数的位置

代码实现（C++11）

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty()) return 0;
        int l, r;
        int i = 0, j = data.size() - 1;
        // 确定l的位置
        while(i < j){
            int mid = i + j >> 1;
            if(data[mid] >= k) j = mid;
            else i = mid + 1;
            }
        l = i;
        if(data[l] < k) l++;    // 若不满足data[l] >= k, l++

        // 确定r的位置
        i = 0, j = data.size() - 1;
        while(i < j){
            int mid = i + j + 1 >> 1;
            if(data[mid] <= k) i = mid;
            else j = mid - 1;
            }
        r = i;
        if(data[r] > k) r--;    // 若不满足data[r] <= k, r--

        return r - l + 1;
    }
};

时间复杂度：O(logn)
空间复杂度：O(1)