剑指offer 数字在排序数组中出现的次数
- 题目描述
统计一个数字在排序数组中出现的次数。
- 题目解答
一看就是二分大法呀!
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int size = data.size();
if (size == 0 || k<data[0] || k>data[size-1])
return 0;
int l = 0, r = size - 1;
int count = 0;
while (l <= r){
int mid = l + (r - l) / 2;
if (data[mid] == k){
count++;
for (int i = mid - 1; i >= 0 && data[i] == k; --i)
count++;
for (int j = mid + 1; j<size&&data[j] == k; ++j)
count++;
break;
}
else if (data[mid] > k){
r = mid - 1;
}
else{
l = mid + 1;
}
}
return count;
}
};