题解 | #数字在升序数组中出现的次数#

描述
统计一个数字在升序数组中出现的次数。
输入：[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>