数字在升序数组中出现的次数（C++）

  给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)

输入：
[1,2,3,3,3,3,4,5],3
返回值：
4

输入：
[1,3,4,5],6
返回值：
0

哈希思想，利用一个足够大的空间记录所有数字出现的次数。

class Solution {
public:
    int GetNumberOfK(vector data ,int k) {
        int num[1000]{0};
        auto begin = data.begin();
        auto end = data.end();
        for(;begin!=end;begin++)
            num[*begin]++;
        return num[k];
    }
};

由于是升序数组，因此可以直接查询到k，并进行统计。

class Solution {
public:
    int GetNumberOfK(vector data ,int k) {
        int res = 0;
        for(int i =0;i
            if(data[i] == k)
            {
                while(i
                    ++res;
                    i++;
                    if(data[i]!=k)
                        break;
                }
            }
        }
        return res;
    }
};