当前位置:网站首页>记某公司面试算法题:查找一个有序数组某个数字出现的次数
记某公司面试算法题:查找一个有序数组某个数字出现的次数
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 operational amplifier 2022-2028: Research Report on technology, participants, trends, market size and share
- [reading notes] rewards efficient and privacy preserving federated deep learning
- FRP intranet penetration
- Esp8266 at+cipstart= "", "", 8080 error closed ultimate solution
- Global and Chinese market for intravenous catheter sets and accessories 2022-2028: Research Report on technology, participants, trends, market size and share
- CSDN问答标签技能树(二) —— 效果优化
- [BMZCTF-pwn] 11-pwn111111
- Database middleware_ MYCAT summary
- CSDN-NLP:基于技能树和弱监督学习的博文难度等级分类 (一)
- MySQL36-数据库备份与恢复
猜你喜欢
Pytorch RNN actual combat case_ MNIST handwriting font recognition
CSDN Q & a tag skill tree (V) -- cloud native skill tree
Other new features of mysql18-mysql8
【博主推荐】C#生成好看的二维码(附源码)
数据库中间件_Mycat总结
Breadth first search rotten orange
A brief introduction to the microservice technology stack, the introduction and use of Eureka and ribbon
Case identification based on pytoch pulmonary infection (using RESNET network structure)
Installation and use of MySQL under MySQL 19 Linux
MySQL28-数据库的设计规范
随机推荐
Copie maître - esclave MySQL, séparation lecture - écriture
CSDN question and answer tag skill tree (I) -- Construction of basic framework
【博主推荐】C#生成好看的二维码(附源码)
Mysql36 database backup and recovery
Mysql25 index creation and design principles
Global and Chinese market of thermal mixers 2022-2028: Research Report on technology, participants, trends, market size and share
[recommended by bloggers] asp Net WebService background data API JSON (with source code)
Yum prompt another app is currently holding the yum lock; waiting for it to exit...
Mysql21 - gestion des utilisateurs et des droits
February 13, 2022-3-middle order traversal of binary tree
Navicat 导出表生成PDM文件
MySQL other hosts cannot connect to the local database
Global and Chinese market of transfer switches 2022-2028: Research Report on technology, participants, trends, market size and share
35 is not a stumbling block in the career of programmers
MySQL35-主从复制
How to find the number of daffodils with simple and rough methods in C language
Mysql23 storage engine
Idea import / export settings file
API learning of OpenGL (2004) gl_ TEXTURE_ MIN_ FILTER GL_ TEXTURE_ MAG_ FILTER
Timestamp with implicit default value is deprecated error in MySQL 5.6