利用二分查找,找出第一次出现的位置和最后一次出现的位置,可以将时间复杂度优化到$O(logn)$。
查找第一个k:用小于k的性质二分,因为满足条件的点一定大于等于k;
第二个k:用小于等于k的性质二分,因为满足条件的点一定小于等于k。
两个端点间的距离即为出现的次数。
–二分模板–
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
if (nums.empty()) return 0;
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;
}
// 如果不等于k, 说明不存在
if (nums[l] != k) return 0;
int left = l; //左端点已查找到
l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r + 1>> 1;
if (nums[mid] <= k) l = mid; //要找的区间应该是右半边,包括端点
else r = mid - 1;
}
int right = r;
return right - left + 1;
}
};