[PHP] 算法-统计一个数字在排序数组中出现的次数的PHP实现

发布时间：2020-05-25 03:10:05 所属栏目：PHP 来源：互联网

导读：统计一个数字在排序数组中出现的次数。1.有序的数组查找，使用二分法2.二分法查找第一次出现的位置，二分法查找最后一次出现的位置，end - start +1left=getLeft(data,k)right=getRight(data,k)retun right-left+1getLeft data,kleft=0right=arr.length-1mid=

1.<span style="color: #000000">有序的数组查找，使用二分法

2.二分法查找第一次出现的位置，二分法查找最后一次出现的位置，<span style="color: #008080">end - start +1<span style="color: #000000">
left=getLeft(data,<span style="color: #000000">k)

right=getRight(data,<span style="color: #000000">k)

retun right-left+1<span style="color: #000000">
getLeft data,<span style="color: #000000">k

left=0<span style="color: #000000">

right=arr.length-1<span style="color: #000000">

mid=left+(right-left)/2

<span style="color: #0000ff">while  left<=<span style="color: #000000">right

<span style="color: #0000ff">if arr[mid]<k    <span style="color: #008000">//<span style="color: #008000">关键

left=mid+1

<span style="color: #0000ff">else<span style="color: #000000">

right=mid-1<span style="color: #000000">

mid=left+(right-left)/2

<span style="color: #0000ff">return<span style="color: #000000"> left

getRight data,<span style="color: #000000">k

left=0<span style="color: #000000">

right=arr.length-1<span style="color: #000000">

mid=left+(right-left)/2

<span style="color: #0000ff">while  left<=<span style="color: #000000">right

<span style="color: #0000ff">if arr[mid]<=k   <span style="color: #008000">//<span style="color: #008000">关键

left=mid+1

<span style="color: #0000ff">else<span style="color: #000000">

right=mid-1<span style="color: #000000">

mid=left+(right-left)/2

<span style="color: #0000ff">return right

{
$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,5);
$m=GetNumberOfK($arr,4);
var_dump($m);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!