PHP zählt, wie oft eine Zahl in einem sortierten Array erscheint

In diesem Artikel wird hauptsächlich die PHP-Methode zum Zählen der Anzahl des Vorkommens einer Zahl in einem sortierten Array vorgestellt. Dabei werden die zugehörigen Betriebsfähigkeiten von PHP zum Suchen und Zählen in Arrays basierend auf dem binären Suchalgorithmus berücksichtigt. Ich hoffe, es kann allen helfen.

Frage

Zählen Sie, wie oft eine Zahl in einem sortierten Array erscheint.

Lösung

Da es sich um ein sortiertes Array handelt, ist die binäre Suche am effizientesten. Sobald Sie es gefunden haben, erweitern Sie es auf beide Seiten.

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;
}

Verwandte Empfehlungen:

Probleme im Zusammenhang mit benutzerdefinierten sortierten Arrays

Ermitteln Sie im sortierten Array die Häufigkeit des Vorkommens einer bestimmten Zahl, zum Beispiel [1, 2, 2, 2, 3 ]

Ordnen Sie das Array entsprechend einem bestimmten Schlüsselwert neu

Das obige ist der detaillierte Inhalt vonPHP zählt, wie oft eine Zahl in einem sortierten Array erscheint. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!