剑指37-数字在排序数组中出现的次数
2023-02-18 16:41:13 时间
二分查找
题目描述
统计一个数字在排序数组中出现的次数。
解法
思想很简单,用二分法在排序数组中找到该数字的位置,再往两边查找
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int binarySort(vector<int> data, int k, int left, int right) //二分查找
{
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (data[mid] == k) return mid;
if (data[mid] > k) return binarySort(data, k, left, mid - 1);
if (data[mid] < k) return binarySort(data, k, mid + 1, right);
}
int GetNumberOfK(vector<int> data, int k) {
int res = 0;
int pos = binarySort(data, k, 0, data.size() - 1);
cout << pos <<endl;
if (pos < 0) return res;
else res = 1;
int left = pos, right = pos;
while (right < data.size() && right + 1 < data.size()) //往右相等的个数
{
if (data[right + 1] == data[right])
{
right++;
res++;
}
else break;
}
while (left >= 0 && left - 1 >= 0) //往左相等的个数
{
if (data[left - 1] == data[left])
{
left--;
res++;
}
else break;
}
return res;
}
};
//void main()
//{
// vector<int> data = { 1,2,3,4,5,6,7 };
// Solution s;
// cout<< s.GetNumberOfK(data, 3);
//
//}
相关文章
- 【架构师(第二十五篇)】编辑器开发之属性编辑区域表单渲染
- 【架构师(第二十六篇)】编辑器开发之属性编辑同步渲染
- 2021年度“CCF-腾讯犀牛鸟基金”发布结题评优结果
- 【架构师(第二十七篇)】前端单元测试框架 Jest 基础知识入门
- 太空噗|重燃太空热潮!与噗噗星人一同探索星海浪漫
- 算法工程师深度解构ChatGPT技术
- 【架构师(第二十八篇)】 测试工具 Vue-Test-Utils 基础语法
- 【架构师(第二十九篇)】Vue-Test-Utils 触发事件和异步请求
- 【架构师(第三十篇)】Vue-Test-Utils 全局组件和第三方库 vuex | vue-router
- 【架构师(第三十一篇)】前端测试之 TDD 的开发方式
- 【架构师(第三十二篇)】 通用上传组件开发及测试用例
- 【架构师(第三十三篇)】 Vue 中的实例及本地图片预览
- 【架构师(第三十四篇)】 业务组件库开发之 vue3 的插件系统
- 【架构师(第三十五篇)】 业务组件库开发之使用 Rollup 进行打包
- 【架构师(第三十六篇)】 业务组件库开发之发布到 NPM
- 【架构师(第四十二篇)】 服务端开发之常用的登录鉴权方式
- 【架构师(第四十三篇)】 服务端开发之单元测试和接口测试
- 【架构师(第四十四篇)】 服务端开发之 pm2 和 nginx 介绍
- 【架构师(第四十六篇)】 服务端开发之安装 Docker
- 【架构师(第四十七篇)】 服务端开发之认识 Docker