[PHP] 算法-统计一个数字在排序数组中出现的次数的PHP实现
2023-02-18 15:47:20 时间
统计一个数字在排序数组中出现的次数。 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);
相关文章
- 工作十余年,还是一直被问 委托和事件 有什么区别? 真是够了
- 用了Dapper之后通篇还是SqlConnection,真的看不下去了
- 一个有趣的问题, 你知道SqlDataAdapter中的Fill是怎么实现的吗
- C# 9.0 终于来了, Top-level programs 和 Partial Methods 两大新特性探究
- Newtonsoft 六个超简单又实用的特性,值得一试 【下篇】
- Newtonsoft 六个超简单又实用的特性,值得一试 【上篇】
- HashSet扩容机制在时间和空间上的浪费,远大于你的想象
- foreach 集合又抛经典异常了,这次一定要刨根问底
- C#9.0 终于来了,带你一起解读 nint 和 Pattern matching 两大新特性玩法
- C#9.0 终于来了,您还学的动吗? 带上VS一起解读吧!(应该是全网第一篇)
- MySql轻松入门系列——第二站 使用visual studio 对mysql进行源码级调试
- 字符串太占内存了,我想了各种奇思淫巧对它进行压缩
- MySql轻松入门系列——第一站 从源码角度轻松认识mysql整体框架图
- 自定义值类型一定不要忘了重写Equals,否则性能和空间双双堪忧
- 使用PInvoke互操作,让C#和C++愉快的交互优势互补
- 阿里短信回执.net sdk的bug导致生产服务cpu 100%排查
- List的扩容机制,你真的明白吗?
- BitArray虽好,但请不要滥用,又一次线上内存暴增排查
- 记一次排查线上程序内存的忽高忽低,又是大集合惹祸了
- 追了多年的开发框架,你还认识指针吗?