>  기사  >  백엔드 개발  >  PHP는 정렬된 배열에 숫자가 나타나는 횟수를 계산합니다.

PHP는 정렬된 배열에 숫자가 나타나는 횟수를 계산합니다.

小云云
小云云원래의
2018-01-15 10:06:291849검색

이 글에서는 정렬된 배열에서 숫자의 발생 횟수를 계산하는 PHP의 방법을 주로 소개합니다. 이진 검색 알고리즘을 기반으로 배열을 검색하고 계산하는 PHP의 관련 조작 기술이 포함되어 있습니다. 그것이 모두에게 도움이 되기를 바랍니다.

Question

정렬된 배열에 숫자가 나타나는 횟수를 셉니다.

Solution

정렬된 배열이므로 이진 검색이 가장 효율적입니다. 찾은 후 양쪽으로 확장하십시오.

Code


<?php
function GetNumberOfK($data, $k)
{
  if(count($data)==0){
    return 0;
  }
  $index = 0;
  $low = 0;
  $high = count($data)-1;
  $middle = 0;
  //二分查找找到k的index
  while($low<=$high){
    $middle = ($high+$low)>>1;
    if($data[$middle]==$k){
      $index = $middle;
      break;
    }
    else if($data[$middle]>$k) {
      $high = $middle -1;
    }else{
      $low = $middle+1;
    }
    $index = -1;
  }
  // console.log(index);
  // 如果没找到
  if($index==-1){
    return 0;
  }
  //找到了 分别往左右查找边界
  $start = $index;
  $end = $index;
  $count = 0;
  while($data[$start]==$k){
    $count++;
    $start--;
  }
  while($data[$end]==$k){
    $count++;
    $end++;
  }
  return $count-1;
}

관련 권장 사항:

사용자 정의 정렬 배열에 대한 질문

정렬된 배열에서 주어진 숫자의 발생 횟수를 찾습니다. 예를 들어 [ 1, 2 , 2, 2, 3]

특정 키 값에 따라 배열을 재정렬

위 내용은 PHP는 정렬된 배열에 숫자가 나타나는 횟수를 계산합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.