最简单的思路是遍历一遍数组，去数一共出现了几个 k，但是时间复杂度会比较高（O(n)）。由于数组中的数字是“排序”的，所以可以使用二分查找来使得时间复杂度降低为 O(log(n))。
在使用二分查找的时候需要注意 right 的初始值是data.size()-1而非data.size()，否则访问可能会越界；而循环条件是 left<=right 而非 left<right，否则在只有两个元素的时候可能会查找失败。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int left=0,right=data.size()-1,middle;
bool isFound=false;
while(left<=right){
middle=(left+right)/2;
if(data[middle]>k) right=middle-1;
else if(data[middle]<k) left=middle+1;
else{
isFound=true;
break;
}
}
int times=0;
if(isFound){
for(int t=middle-1;t>=0 && data[t]==k;t--) times++;
for(int t=middle+1;t<data.size() && data[t]==k;t++) times++;
times++;
}
return times;
}
};
|
PS：STL 中的 vector 没有 length() 方法，只有 size() 方法，而 string 两种方法都有。
另外，看了一下书以后发现，我使用的方法虽然和书上思想一样，但是要比 getFirstK 和 getLastK 要方便很多。