PHP compte le nombre de fois qu'un nombre apparaît dans un tableau trié

小云云
Libérer: 2023-03-19 14:24:01
original
1857 Les gens l'ont consulté

Cet article présente principalement la méthode PHP de comptage du nombre d'occurrences d'un nombre dans un tableau trié, impliquant les compétences opérationnelles associées de PHP pour rechercher et compter dans des tableaux basés sur l'algorithme de recherche binaire. Les amis qui en ont besoin peuvent s'y référer. J'espère que cela pourra aider tout le monde.

Question

Comptez le nombre de fois qu'un nombre apparaît dans un tableau trié.

Solution

Comme il s'agit d'un tableau trié, la recherche binaire est la plus efficace. Après l'avoir trouvé, développez-le des deux côtés.

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;
}
Copier après la connexion

Recommandations associées :

Problèmes liés aux tableaux triés définis par l'utilisateur

Dans le tableau trié, recherchez le nombre d'occurrences d'un nombre donné Par exemple, [1, 2, 2, 2, 3. ]

Réorganiser le tableau en fonction d'une certaine valeur clé

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!