与算法基础课模板题一致
链接 https://www.acwing.com/problem/content/791/
法一:暴力
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
int number = 0;
for (int x : nums)
{
if (x == k) number ++;
}
return number;
}
};
法二:二分
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
int n = nums.size();
if (!n) return 0;
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if (nums[mid] >= k) r = mid;
else l = mid + 1;
}
int a = 0, b = 0;
if (nums[l] != k) return 0;
a = r;
l = 0, r = n - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (nums[mid] <= k) l = mid;
else r = mid - 1;
}
b = r;
return b - a + 1;
}
};