이 기사의 내용은 정렬된 배열(코드)에 숫자가 나타나는 횟수를 계산하는 방법에 대한 내용입니다. 필요한 참조 값이 있으면 도움이 되길 바랍니다.
정렬된 배열에 숫자가 나타나는 횟수를 셉니다.
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!