经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » PHP » 查看文章
[PHP] 算法-统计一个数字在排序数组中出现的次数的PHP实现
来源:cnblogs  作者:陶士涵  时间:2018/9/25 20:37:41  对本文有异议
  1. 统计一个数字在排序数组中出现的次数。
  2. 1.有序的数组查找,使用二分法
  3. 2.二分法查找第一次出现的位置,二分法查找最后一次出现的位置,end - start +1
  4. left=getLeft(data,k)
  5. right=getRight(data,k)
  6. retun right-left+1
  7. getLeft data,k
  8. left=0
  9. right=arr.length-1
  10. mid=left+(right-left)/2
  11. while left<=right
  12. if arr[mid]<k //关键
  13. left=mid+1
  14. else
  15. right=mid-1
  16. mid=left+(right-left)/2
  17. return left
  18. getRight data,k
  19. left=0
  20. right=arr.length-1
  21. mid=left+(right-left)/2
  22. while left<=right
  23. if arr[mid]<=k //关键
  24. left=mid+1
  25. else
  26. right=mid-1
  27. mid=left+(right-left)/2
  28. return right
  1. <?php
  2. function GetNumberOfK($data, $k)
  3. {
  4. $left=getLeft($data,$k);
  5. $right=getRight($data,$k);
  6. return $right-$left+1;
  7. }
  8. function getLeft($arr,$k){
  9. $left=0;
  10. $right=count($arr)-1;
  11. $mid=intval($left+($right-$left)/2);
  12. while($left<=$right){
  13. if($arr[$mid]>=$k){//关键
  14. $right=$mid-1;
  15. }else{
  16. $left=$mid+1;
  17. }
  18. $mid=intval($left+($right-$left)/2);
  19. }
  20. return $left;
  21. }
  22. function getRight($arr,$k){
  23. $left=0;
  24. $right=count($arr)-1;
  25. $mid=intval($left+($right-$left)/2);
  26. while($left<=$right){
  27. if($arr[$mid]<=$k){//关键
  28. $left=$mid+1;
  29. }else{
  30. $right=$mid-1;
  31. }
  32. $mid=intval($left+($right-$left)/2);
  33. }
  34. return $right;
  35. }
  36. $arr=array(1,2,3,4,4,4,5);
  37. $m=GetNumberOfK($arr,4);
  38. var_dump($m);

 

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号