[PHP] 算法-统计一个数字在排序数组中出现的次数的PHP实现
2023-02-18 15:41:47 时间
统计一个数字在排序数组中出现的次数。 1.有序的数组查找,使用二分法 2.二分法查找第一次出现的位置,二分法查找最后一次出现的位置,end - start +1 left=getLeft(data,k) right=getRight(data,k) retun right-left+1 getLeft data,k left=0 right=arr.length-1 mid=left+(right-left)/2 while left<=right if arr[mid]<k //关键 left=mid+1 else right=mid-1 mid=left+(right-left)/2 return left getRight data,k left=0 right=arr.length-1 mid=left+(right-left)/2 while left<=right if arr[mid]<=k //关键 left=mid+1 else right=mid-1 mid=left+(right-left)/2 return right
<?php function GetNumberOfK($data, $k) { $left=getLeft($data,$k); $right=getRight($data,$k); return $right-$left+1; } function getLeft($arr,$k){ $left=0; $right=count($arr)-1; $mid=intval($left+($right-$left)/2); while($left<=$right){ if($arr[$mid]>=$k){//关键 $right=$mid-1; }else{ $left=$mid+1; } $mid=intval($left+($right-$left)/2); } return $left; } function getRight($arr,$k){ $left=0; $right=count($arr)-1; $mid=intval($left+($right-$left)/2); while($left<=$right){ if($arr[$mid]<=$k){//关键 $left=$mid+1; }else{ $right=$mid-1; } $mid=intval($left+($right-$left)/2); } return $right; } $arr=array(1,2,3,4,4,4,5); $m=GetNumberOfK($arr,4); var_dump($m);
相关文章
- [PHP] 适配器模式-结构型设计模式
- [PHP] 静态工厂模式-创建型设计模式
- [PHP] 单例模式-创建型设计模式
- [PHP] 简单工厂模式-创建型设计模式
- [PHP] 原型模式-创建型设计模式
- [PHP] 对象池模式-创建型设计模式
- [Laravel系列] 验证规则required_without_all 的使用
- [PHP] 工厂方法设计模式-创建型设计模式
- [PHP] 生成器模式-创建型设计模式
- [Laravel系列] 在线客服系统代码优化-配置mysql数据库读写分离
- [PHP] 抽象工厂设计模式-创建型设计模式
- [Laravel系列] 在Laravel ORM 使用STRAIGHT_JOIN
- [MySQL系列] SELECT STRAIGHT_JOIN优化join查询技巧
- [PHP] 新浪企业邮箱登录功能难点梳理
- [MySQL系列] 使用STRAIGHT_JOIN 优化inner join查询排序索引问题
- [Laravel系列] 解决laravel中paginate()与distinct() count语句错误问题
- [Laravel系列] 框架中增加记录access log的日志中间件
- [Laravel系列] 解决Laravel中NotFoundHttpException异常
- [MySQL] 利用explain查看sql语句中使用的哪个索引
- [前端] 设定为disabled的表单域值不能被提交