PHP实现统计一个数字在排序数组中出现次数的方法
这篇文章主要介绍了PHP实现统计一个数字在排序数组中出现次数的方法,涉及php基于二分查找算法在数组中进行查找及统计的相关操作技巧,需要的朋友可以参考下。
本文实例讲述了PHP实现统计一个数字在排序数组中出现次数的方法，分享给大家供大家参考，具体如下：
题目
统计一个数字在排序数组中出现的次数。
题解
既然是排序数组，使用二分查找是效率最高的，找到之后再向两侧拓展一下。
代码：
- <?php
- function GetNumberOfK($data, $k)
- {
- if(count($data)==0){
- return 0;
- }
- $index = 0;
- $low = 0;
- $high = count($data)-1;
- $middle = 0;
- //二分查找找到k的index
- while($low<=$high){
- $middle = ($high+$low)>>1;
- if($data[$middle]==$k){
- $index = $middle;
- break;
- }
- else if($data[$middle]>$k) {
- $high = $middle -1;
- }else{
- $low = $middle+1;
- }
- $index = -1;
- }
- // console.log(index);
- // 如果没找到
- if($index==-1){
- return 0;
- }
- //找到了 分别往左右查找边界
- $start = $index;
- $end = $index;
- $count = 0;
- while($data[$start]==$k){
- $count++;
- $start--;
- }
- while($data[$end]==$k){
- $count++;
- $end++;
- }
- return $count-1;
- }