剑指Offer-36.数字在排序数组中出现的次数(C++/Java)
2024-10-18 05:17:58
题目：
统计一个数字在排序数组中出现的次数。
分析：
给定一个已经排好序的数组，统计一个数字在数组中出现的次数。
那么最先想到的可以遍历数组统计出现的次数，不过题目给了排序数组，那么一定是利用了排序这个性质来缩减时间复杂度的。
因为如果所给的数字在数组中出现，那么这个数字在数组中一定是连续的，那么可以利用二分查找所给出的数字的首尾索引。
程序：
C++
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
if(data.size() == ){
return ;
}
int l = FindFirst(data, k, , data.size()-);
int r = FindEnd(data, k, , data.size()-);
if(r != - && l != -)
return r-l+;
else
return ;
}
int FindFirst(vector<int> &data ,int k, int left, int right){
if(left > right)
return -;
int mid = left + (right - left) / ;
if(data[mid] == k){
if((mid > && data[mid-] != k) || mid == )
return mid;
else
right = mid - ;
}
else if(data[mid] < k){
left = mid + ;
}
else{
right = mid -;
}
return FindFirst(data, k, left, right);
}
int FindEnd(vector<int> &data ,int k, int left, int right){
if(left > right)
return -;
int mid = left + (right - left) / ;
if(data[mid] == k){
if((mid < data.size()- && data[mid+] != k) || mid == data.size()-)
return mid;
else
left = mid + ;
}
else if(data[mid] < k){
left = mid + ;
}
else{
right = mid -;
}
return FindEnd(data, k, left, right);
}
};
Java
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length == 0){
return 0;
}
int l = FindFirst(array, k, 0, array.length-1);
int r = FindEnd(array, k, 0, array.length-1);
if(r != -1 && l != -1)
return r-l+1;
else
return 0;
}
int FindFirst(int [] array ,int k, int left, int right){
if(left > right)
return -1;
int mid = left + (right - left) / 2;
if(array[mid] == k){
if((mid > 0 && array[mid-1] != k) || mid == 0)
return mid;
else
right = mid - 1;
}
else if(array[mid] < k){
left = mid + 1;
}
else{
right = mid -1;
}
return FindFirst(array, k, left, right);
}
int FindEnd(int [] array ,int k, int left, int right){
if(left > right)
return -1;
int mid = left + (right - left) / 2;
if(array[mid] == k){
if((mid < array.length-1 && array[mid+1] != k) || mid == array.length-1)
return mid;
else
left = mid + 1;
}
else if(array[mid] < k){
left = mid + 1;
}
else{
right = mid -1;
}
return FindEnd(array, k, left, right);
}
}
最新文章
- echarts引入及应用
- iOS阶段学习第二天笔记(数据类型与进制)
- zepto的tap事件的穿透分析
- Mina小例子
- GCD的使用和面试题集锦
- Kafka 0.10 KafkaConsumer流程简述
- 高性能JavaScript（1）
- 乐乐课堂_leleketang.com
- EF6学习笔记（四） 弹性连接及命令拦截调试
- Python操作Influxdb数据库
- javaWEB登录ajax传值
- 【题解】 bzoj4033: [HAOI2015]树上染色* （动态规划）
- nginx 跨域配置
- C/C++服务器开发的必备利器–libconfig
- mysql 数据操作 单表查询 通过四则运算查询
- python学习笔记（十七）网络编程之urllib模块
- spark SQL学习（数据源之json）
- [Maven实战-许晓斌]-[第二章]-2.6 NetBeans上面安装Maven插件
- 【shiro】关于shiro匹配URL的小用法
- 教你用webgl快速创建一个小世界
热门文章
- Flask 教程 第十二章：日期和时间
- Mac Electron 应用的签名（signature）和公证（notarization）
- mysql创建用户后无法进入
- 推荐一个好用的行内可编辑的table组件 vxe-table
- linux 执行 javac 报错 javac: command not found
- spring boot 2.2.0开始freemarker模板默认扩展名改为ftlh了
- JavaScript-----8.数组
- HashMap、HashTable 和 ConcurrentHashMap 线程安全问题
- ReactNative: 使用导航栏组件-NavigatorIOS组件和Navigator组件
- thinkphp5.0学习笔记