描述
统计一个数字在升序数组中出现的次数。
输入:[1,2,3,3,3,3,4,5],3
返回值:4
小结:对于数组统计每个元素出现的次数,比如:输出重复数字,重复数字出现次数大于数组元素个数的一半等,均可以使用hash表的方法来实现。
方法一:hash表法
int GetNumberOfK(vector<int> data ,int k) {
unordered_map<int, int>map;
for(int i = 0; i < data.size(); i++)
{
map[data[i]]++;
}
return map[k];
}
时间复杂度:O(n)
空间复杂度:O(n)</int>

方法二:暴力法
int GetNumberOfK(vector<int> data ,int k) {
int count = 0;
for(int i = 0; i < data.size(); i++)
{
if(data[i] == k) count++;
}
return count;
}
时间复杂度:O(n)
空间复杂度:O(1)</int>

方法三:使用库函数lower_bound(),upper_bound(),由于底层是二分查找,因此时间复杂度降低。
lower_bound(begin,end,num):返回第一次出现大于等于num的地址;begin是用于比较的首地址,end是比较的结尾地址。
upper_bound(begin,end,num):返回第一次出现大于num的数的地址;
注意返回的不是数,是地址,不能用int来定义获得的数值,使用auto。
int GetNumberOfK(vector<int> data ,int k) {
auto l = lower_bound(data.begin(), data.end(), k);
auto r = upper_bound(data.begin(), data.end(), k);
return r - l;
}</int>

时间复杂度:O(logN)
空间复杂度:O(1)

方法四:题目中说数组有序,第一反应应该是使用二分法。下面使用的是官方解法。
两次使用二分法找到对应的左右边界,而都是从左指针进行出发,唯一的不同是判定条件,就很神奇。
int GetNumberOfK(vector<int> data ,int k) {
int lbound = 0, rbound = 0;
int l = 0, r = data.size();
//寻找上界
while(l < r)
{
int mid = l+(r-l)/2;
if(data[mid] < k)
{
l = mid + 1;
}
else{
r = mid;
}
}
lbound = l;
//寻找下界
l = 0, r = data.size();
while(l < r)
{
int mid = l+(r-l)/2;
if(data[mid] <= k)
{
l = mid + 1;
}
else{
r = mid;
}
}
rbound = l;
return rbound-lbound;
}
时间复杂度:O(logN)
空间复杂度:O(1)
备注:二分法自己还要细细体会一番啊。</int>