解法一（哈希法）

思想

很显然，把数组中的数放到一个哈希表中，然后返回k对应的次数。

代码实例

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //哈希
        unordered_map<int,int> mp;
        for(int i = 0;i<data.size();++i)
        {
        	++mp[data.at(i)];
        }
        return mp[k];
    }
};

解法二（二分法）

思想

上述方法没有用到数组非降序的性质，很显然对于有序数组我们可以使用二分法。由于k出现后一定是连续的，这里利用二分查找找k-0.5的位置和k+0.5的位置，这样k出现的次数就是这两个位置相减后得到的值。

代码实例

class Solution {
public:    
	int bSearch(vector<int> &vec, double k)
	{
		int start = 0;
		int end = vec.size() - 1;
		while (start <= end)
		{
			int mid = (start + end);
			
			if (k < vec[mid])
			{
				end = mid - 1;
			}
			else
			{
				start = mid + 1;
			}
		}
		
		return start;
	}
	
    int GetNumberOfK(vector<int> vec ,int k) {
        int start = bSearch(vec, k - 0.5);
        int end = bSearch(vec, k + 0.5);
		return end - start;
    }
};