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

yipeiwu_com6年前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;
}

PS:这里再为大家推荐2款功能类似的统计工具(JS实现)供大家参考使用:

在线字数统计工具:
http://tools.jb51.net/code/zishutongji

在线字符统计与编辑工具:
http://tools.jb51.net/code/char_tongji

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》及《php程序设计算法总结

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

相关文章

php中将一段数据存到一个txt文件中并显示其内容

这里的数据可以为基本数据类型,数组,对象等; 在存储的时候可以用serialize进行序列化,但取的时候要先用unserialize反序列化。 <?php $dat...

解析php中反射的应用

一  反射的使用: 复制代码 代码如下:<?phpclass Person{ public $name; function __construct($...

PHP过滤★等特殊符号的正则

复制代码 代码如下: if(preg_match("/[ '.,:;*?~`!@#$%^&+=)(<>{}]|\]|\[|\/|\\\|\"|\|/",$user)){ ec...

PHP实现SMTP邮件的发送实例

当你还在纠结php内置的mail()函数不能发送邮件时,那么你现在很幸运,此时的这篇文章可以帮助到你! php利用smtp类来发邮件真是屡试不爽,我用过很久了,基本上没出过问题。本博客后...

php查询whois信息的方法

本文实例讲述了php查询whois信息的方法。分享给大家供大家参考。具体如下: 这里使用php通过查询whois信息的网站列表进行查询 function whois_query($d...