So zählen Sie, wie oft eine Zahl in einem sortierten Array in PHP erscheint (Code)

Der Inhalt dieses Artikels handelt davon, wie PHP die Häufigkeit zählen kann, mit der eine Zahl in einem sortierten Array (Code) erscheint. Ich hoffe, dass er für Freunde in Not hilfreich ist du hilfst.

Zählen Sie, wie oft eine Zahl im sortierten Array erscheint.
1. Geordnete Array-Suche, binäre Methode verwenden
2. Binäre Methode, um die Position des ersten Vorkommens zu finden, binäre Methode, um die Position des letzten Vorkommens zu finden, Ende - 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);

Das obige ist der detaillierte Inhalt vonSo zählen Sie, wie oft eine Zahl in einem sortierten Array in PHP erscheint (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!