题目描述
统计一个数字在排序数组中出现的次数。
例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3,由于3在这个数组中出现了4次,因此输出4。
样例
输入:[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出:4
算法1
哈希表 $O(n)$
每次遇到这种类型的题,就不由的想到哈希做,因为想下意识的训练一下哈希,思路很简单,把数组遍历一遍,存进哈希表
然后用迭代器遍历哈希表,输出目标是出现的次数即可。
时间复杂度
时间复杂度应该是$O(n)$吧,我对时间复杂度一直分析的不是很好,如有错误, 多多指教,第一次写题解。。。。
参考文献
参考文献的话,就是y总的视频, emmm
C++ 代码
class Solution {
public:
unordered_map<int, int> h;
int getNumberOfK(vector<int>& nums , int k) {
int res = 0;
for(int i = 0; i < nums.size(); i++) h[nums[i]]++;
for(unordered_map<int, int>::iterator it = h.begin(); it != h.end(); it++)
if(it->first == k) res = it->second;
return res;
}
};