剑指offer编程题解法汇总37-数字在排序数组中出现的次数
2023-09-11 14:18:52 时间
题目描述
统计一个数字在升序数组中出现的次数。
示例1
输入
[1,2,3,3,3,3,4,5],3
返回值
4
想法自然是二分查找,代码如下:
/**
* [],3
* 4
*/
public int GetNumberOfK(int[] array, int k) throws Exception {
try{
int binarysearchIndex = binarysearch(array, k);
int num = 1;
int middle = binarysearchIndex;
while ((--middle >= 0) && array[middle] == k) {
num++;
}
while ((++binarysearchIndex <= (array.length - 1)) && array[binarysearchIndex] == k) {
num++;
}
return num;
}catch (Exception e){
}
return 0;
}
/**
* 二分查找找位置
*/
public int binarysearch(int[] array, int k) throws Exception {
if (k < array[0] || k > array[array.length - 1]) {
throw new Exception("error");
}
int start = 0;
int end = array.length - 1;
int middle = 0;
while (true) {
middle = (start + end) / 2;
if (k == array[middle]) {
break;
}
if (start == end) {
throw new Exception("error");
}
if ((end - start) == 1) {
// 直接判断
if (array[start] == k) {
return start;
} else if (array[end] == k) {
return end;
} else {
throw new Exception("error");
}
}
if (array[middle] > k) {
end = middle;
} else {
start = middle;
}
}
return middle;
}
测试代码:
public static void main(String[] args) {
Solution solution = new Solution();
int[] arrays = {1, 1, 1, 1, 1,2};
int binarysearch = 99;
try {
binarysearch = solution.GetNumberOfK(arrays, 3);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println(binarysearch);
}
相关文章
- Python网络编程之TCP套接字简单用法示例
- 面向切面编程AOP[二](java @EnableAspectJAutoProxy 代码原理)
- Linux Shell脚本自动化编程实战- Array数组
- scratch编程
- 在SAP云平台ABAP编程环境上编写第一段ABAP程序
- Qt 网络编程:QNetworkAccessManager
- 新手程序员如何提升自己的编程能力
- 分享写python需要养成的9个编程好习惯,希望给你们带来帮助~
- 面向“运维”编程,不考虑运营成本的编码都是耍流氓!
- java笔记:流式编程 数组与List集合互转
- Python编程:ndarray数组的保存与读取
- VB编程:利用数组统计文字段落数-31
- VB编程:UBound获取数组上限;LBound获取数组下限-25
- VB编程:利用数组实现矩阵转换-28_彭世瑜_新浪博客
- VB编程:申明窗体数组-40_彭世瑜_新浪博客
- VB编程:利用二位数组MSHFlexGrid表格添加数据-33
- 【编程实践】这个代码命名规范是真优雅呀!代码如诗!!(多读优秀的开源代码,多实践,你也可以一样优秀!)
- 【编程实践】Golang 字符串数组排序
- 【编程实践】构建一个伟大的软件:Build a Great Software
- 【动画详解原理系列】2.多线程并发编程与锁
- 编程之美2.17 数组循环移位
- 38.第六章 Shell脚本编程高级进阶 -- 脚本相关工具和数组(三)
- Aop面向方面编程之PostSharp框架
- 用Java代码编程实现模拟机器人对话
- 修正:C++编程经验(7):delete之后到底要不要置空?
- 详解UNIX环境高级编程---精灵进程