统计一个数字在排序数组中出现的次数。 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);
如对本文有疑问, 点击进行留言回复!!
网友评论