当前位置:网站首页>记某公司面试算法题:查找一个有序数组某个数字出现的次数
记某公司面试算法题:查找一个有序数组某个数字出现的次数
2022-07-06 09:13:00 【三笠·阿卡曼】
记录
记某公司面试算法题:查找一个有序数组某个数字出现的次数,要求是不能使用暴力破解的方式;
本来知道怎么做,结果因为不会写二分导致没手撕出来,着实够菜的。。
代码
package com.vleus.algorithm.strings;
/** * @author vleus * @date 2021年09月26日 20:26 */
public class GetNumCount {
// public static int getNumCount(int[] array, int num) {
//
// if (array.length == 0) {
// return 0;
// }
//
// int count = 0;
// for (int i = 0; i < array.length; i++) {
// if (array[i] == num) {
// count++;
// }
// }
//
// return count;
// }
//二分查找
private static int times(int[] arr, int n) {
int low = 0;
int high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] >= n) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
public static int getNumCount2(int[] arr, int num) {
int first = times(arr, num);
int last = times(arr, num + 1);
int times = (first == arr.length || arr[first] != num) ? 0 : last - first;
return times;
}
public static void main(String[] args) {
int[] arr = {
1, 2, 3, 3, 3, 4, 5};
System.out.println(getNumCount2(arr,6));
}
}
边栏推荐
- Global and Chinese market of wafer processing robots 2022-2028: Research Report on technology, participants, trends, market size and share
- La table d'exportation Navicat génère un fichier PDM
- MySQL26-性能分析工具的使用
- Mysql35 master slave replication
- MySQL19-Linux下MySQL的安装与使用
- Mysql32 lock
- Are you monitored by the company for sending resumes and logging in to job search websites? Deeply convinced that the product of "behavior awareness system ba" has not been retrieved on the official w
- February 13, 2022-2-climbing stairs
- MySQL27-索引优化与查询优化
- CSDN问答标签技能树(一) —— 基本框架的构建
猜你喜欢
随机推荐
MySQL26-性能分析工具的使用
Nanny hand-in-hand teaches you to write Gobang in C language
MySQL21-用户与权限管理
Advantages and disadvantages of evaluation methods
MySQL34-其他数据库日志
[BMZCTF-pwn] 12-csaw-ctf-2016-quals hungman
Generate PDM file from Navicat export table
How to change php INI file supports PDO abstraction layer
Install MySQL for Ubuntu 20.04
35 is not a stumbling block in the career of programmers
【博主推荐】C#生成好看的二维码(附源码)
Global and Chinese market of wafer processing robots 2022-2028: Research Report on technology, participants, trends, market size and share
Some problems in the development of unity3d upgraded 2020 VR
数据库中间件_Mycat总结
MySQL24-索引的数据结构
MySQL28-数据库的设计规范
MySQL35-主从复制
Database middleware_ MYCAT summary
CSDN blog summary (I) -- a simple first edition implementation
Postman environment variable settings