剑指offer三十七之数字在排序数组中出现的次数
2024-08-26 12:03:28
一、题目
统计一个数字在排序数组中出现的次数。
二、思路
解法一：遍历数组计数
解法二：考虑到时有序数组，所以采用分查找，找到第一个K 和 最后一个K的位置， 二者相减。
三、代码
解法一：
public int GetNumberOfK(int[] array, int k) {
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == k) {
count++;
}
}
return count;
}
解法二：
public class Solution2 {
public int GetNumberOfK(int[] array, int k) {
int lower = getLower(array, k);
int upper = getUpper(array, k);
return upper - lower + 1;
}
//获取k第一次出现的下标
public int getLower(int[] array, int k) {
int start = 0, end = array.length - 1;
int mid = (start + end) / 2;
while (start <= end) {
if (array[mid] < k) {
start = mid + 1;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
return start;
}
//获取k最后一次出现的下标
int getUpper(int[] array, int k) {
int start = 0, end = array.length - 1;
int mid = (start + end) / 2;
while (start <= end) {
if (array[mid] <= k) {
start = mid + 1;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
return end;
}
}
---------------------------------------------
参考链接：
https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2
最新文章
- centos 基本调优
- BaseAdapter的getView()方法
- jsp网站环境搭建
- 远程操控软件 TeamViewer for MAC 官方中文版11.0.55321
- 边工作边刷题：70天一遍leetcode: day 71-3
- ORA-00931: missing identifier ORA-06512: at "SYS.DBMS_UTILITY"
- Eclispe 安装PropertiesEditor插件
- while循环中不支持循环使用curl
- Linux中命令行编译java接口总是提示找不到符号的疑难杂症的解决
- ruby 知识点
- 办理滑铁卢大学(本科)学历认证『微信171922772』UW学位证成绩单使馆认证University of Waterloo
- maven核心概念--插件和目标
- js转换时间戳-转换成 yyyy-MM-dd HH:mm:ss
- Node+GitLab实现小程序CI系统
- PC版收音机—龙卷风收音机
- 3/5/2014 cfb 小心
- Java 8 Lambda表达式，让你的代码更简洁
- php7.0编译安装
- Selenium应用代码（读取mysql表数据登录）
- java源码阅读StringBuilder