AcWing 67. 数字在排序数组中出现的次数
原题链接
简单
作者:
Scathon
,
2021-03-24 09:36:19
,
所有人可见
,
阅读 519
算法1
(暴力枚举) $O(n)$
C++ 代码
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
int cnt = 0;
bool find = false;
for (auto n : nums)
{
if (n == k) cnt++;
else if (cnt) return cnt;
return cnt;
}
};
算法2
(二分) logn
C++ 代码
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
if (nums.empty()) return 0;
int l = find_lower_bound(nums, k);
int r = find_upper_bound(nums, k);
if (nums[l] != k && nums[r] != k) return 0;
return r - l + 1;
}
int find_upper_bound(vector<int>& nums, int k)
{
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (nums[mid] > k) r = mid - 1;
else l = mid;
}
return l;
}
int find_lower_bound(vector<int>& nums, int k)
{
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = (l + r) >> 1;
if (nums[mid] < k) l = mid + 1;
else r = mid;
}
return l;
}
};