这篇文章主要介绍了PHP实现统计一个数字在排序数组中出现次数的方法,涉及php基于二分查找算法在数组中进行查找及统计的相关操作技巧,需要的朋友可以参考下。

本文实例讲述了PHP实现统计一个数字在排序数组中出现次数的方法，分享给大家供大家参考，具体如下：

题目

统计一个数字在排序数组中出现的次数。

题解

既然是排序数组，使用二分查找是效率最高的，找到之后再向两侧拓展一下。

代码：

1. <?php 
2. function GetNumberOfK($data, $k) 
3. { 
4.   if(count($data)==0){ 
5.     return 0; 
6.   } 
7.   $index = 0; 
8.   $low = 0; 
9.   $high = count($data)-1; 
10.   $middle = 0; 
11.   //二分查找找到k的index 
12.   while($low<=$high){ 
13.     $middle = ($high+$low)>>1; 
14.     if($data[$middle]==$k){ 
15.       $index = $middle; 
16.       break; 
17.     } 
18.     else if($data[$middle]>$k) { 
19.       $high = $middle -1; 
20.     }else{ 
21.       $low = $middle+1; 
22.     } 
23.     $index = -1; 
24.   } 
25.   // console.log(index); 
26.   // 如果没找到 
27.   if($index==-1){ 
28.     return 0; 
29.   } 
30.   //找到了 分别往左右查找边界 
31.   $start = $index; 
32.   $end = $index; 
33.   $count = 0; 
34.   while($data[$start]==$k){ 
35.     $count++; 
36.     $start--; 
37.   } 
38.   while($data[$end]==$k){ 
39.     $count++; 
40.     $end++; 
41.   } 
42.   return $count-1; 
43. }

Tags: PHP排序数组

分享到：