剑指Offer——数字在排序数组中出现的次数
2024-09-03 04:02:37
题目描述：
统计一个数字在排序数组中出现的次数。
分析：
二分变形。二分查找最左边和最右边k的位置，然后相减加一就是结果。
代码：
class Solution {
public:
int GetNumberOfK(vector<int> data, int k) {
int dataSize = data.size();
if(dataSize == ) return ;
int firstK = GetPositionOfFirstK(data, k, , dataSize - );
if(firstK == -) return ; // k不存在
int lastK = GetPositionOfLastK(data, k, , dataSize - );
return lastK - firstK + ;
}
int GetPositionOfFirstK(vector<int> data, int k, int left, int right) { // 二分找最左的k的位置
int mid = (left + right) >> ;
while(left < right) {
if(data[mid] > k) {
right = mid - ;
} else if(data[mid] < k) {
left = mid + ;
} else {
if(data[left] != k) left++;
else return left;
right = mid;
}
mid = (left + right) >> ;
}
return data[mid] == k ? mid : -;
}
int GetPositionOfLastK(vector<int> data, int k, int left, int right) { // 二分找最右的k的位置
int mid = (left + right) >> ;
while(left < right) {
if(data[mid] < k) {
left = mid + ;
} else if(data[mid] > k) {
right = mid - ;
} else {
if(data[right] != k) right--;
else return right;
left = mid;
}
mid = (left + right) >> ;
}
return data[mid] == k ? mid : -;
}
};
最新文章
- TODO：Linux安装PHP MongoDB驱动
- Reactjs的Controller View模式
- MFC编程入门之二十七（常用控件：图片控件PictureControl）
- PHPExcel读取Excel文件的实现代码
- bootstrap日期控件在火狐下的模态框中选择时间下拉菜单无效的解决办法
- mysql基本sql语句大全(提升用语篇)
- MSBuild和Jenkins搭建持续集成环境
- AJAX请求也会重新刷新整个页面？
- Docker 监控实战
- PHP微信公众号 access_token缓存
- 关于android:focusable属性
- 例10-3 uva10375（唯一分解定理）
- Quartz学习--二 Hello Quartz! 和源码分析
- Day 4 变量常量
- iPhone内存溢出——黑白苹果
- quartz.net的使用
- ppt点击文字出现图片,再次点击消失
- windows下使用mongodb
- bzoj 3685: 普通van Emde Boas树
- 遍历Map集合四中方法