题目描述
统计一个数字在排序数组中出现的次数。
例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3,由于3在这个数组中出现了4次,因此输出4。
样例
输入:[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出:4
直接利用stl里面的二分查找
lower_bound和upper_bound
lower就是返回第一个大于等于v的值
而upper返回大于v的一个值
因为原数组是排好序的
那么我们就可以直接进行二分查找
即lower返回的是第一个数字
upper返回的是最后一个数字的下一个
直接用upper-lower即为所求
C++ 代码
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
if(nums.empty()) return 0;
int l=lower_bound(nums.begin(),nums.end(),k)-nums.begin();
int r=upper_bound(nums.begin(),nums.end(),k)-nums.begin();
return abs(l-r);
}
};
upper_bound和lower_bound返回的都是对应值num的 地址 ,然后分别用得到的地址跟 nums.begin() 【即第一个元素地址】相减得到 num在数组的下标了 (好像是这样????)
tql
库函数着实不错啊
确实