欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

php如何实现统计一个数字在排序数组中出现的次数(代码)

程序员文章站 2022-03-15 09:02:03
...
本篇文章给大家带来的内容是关于php如何实现统计一个数字在排序数组中出现的次数(代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

统计一个数字在排序数组中出现的次数。
1.有序的数组查找,使用二分法
2.二分法查找第一次出现的位置,二分法查找最后一次出现的位置,end - start +1

left=getLeft(data,k)
right=getRight(data,k)
retun right-left+1
getLeft data,k
    left=0
    right=arr.length-1
    mid=left+(right-left)/2
    while  left<=right
        if arr[mid]<k    //关键
            left=mid+1
        else
            right=mid-1
        mid=left+(right-left)/2
    return left
getRight data,k
    left=0
    right=arr.length-1
    mid=left+(right-left)/2
    while  left<=right
        if arr[mid]<=k   //关键
            left=mid+1
        else
            right=mid-1
        mid=left+(right-left)/2
    return right
<?php
function GetNumberOfK($data, $k) 
{
        $left=getLeft($data,$k);
        $right=getRight($data,$k);
        return $right-$left+1;
}
function getLeft($arr,$k){
        $left=0;
        $right=count($arr)-1;
        $mid=intval($left+($right-$left)/2);
        while($left<=$right){
                if($arr[$mid]>=$k){//关键
                        $right=$mid-1;
                }else{
                        $left=$mid+1;
                }   
                $mid=intval($left+($right-$left)/2);
        }   
        return $left;
}
function getRight($arr,$k){
        $left=0;
        $right=count($arr)-1;
        $mid=intval($left+($right-$left)/2);
        while($left<=$right){
                if($arr[$mid]<=$k){//关键
                        $left=$mid+1;
                }else{
                        $right=$mid-1;
                }   
                $mid=intval($left+($right-$left)/2);
        }   
        return $right;
}
$arr=array(1,2,3,4,4,4,5);
$m=GetNumberOfK($arr,4);
var_dump($m);

以上就是php如何实现统计一个数字在排序数组中出现的次数(代码)的详细内容,更多请关注其它相关文章!

相关标签: php