服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - PHP教程 - PHP实现统计一个数字在排序数组中出现次数的方法

PHP实现统计一个数字在排序数组中出现次数的方法

2019-10-26 14:57重口味AC PHP教程

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

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

题目

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

题解

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

代码

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

希望本文所述对大家PHP程序设计有所帮助。

延伸 · 阅读

精彩推荐