您的位置 首页 php

「php」php如何实现统计一个数字在排序数组中出现的次数(面试题)

本篇文章给大家带来的内容是关于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」php如何实现统计一个数字在排序数组中出现的次数(面试题)

文章地址:https://www.zhihuclub.com/77147.shtml

关于作者: 智云科技

热门文章

网站地图