So implementieren Sie den Algorithmus zum Finden der Zahl mit dem kleinsten Absolutwert in einem geordneten Array in PHP

Dieser Artikel stellt hauptsächlich den PHP-Algorithmus zum Finden der Zahl mit dem kleinsten Absolutwert in einem geordneten Array vor und analysiert kurz die zugehörigen Betriebstechniken von Array-Traversal- und binären Suchalgorithmen. Freunde in Not können sich darauf beziehen

Das Beispiel in diesem Artikel beschreibt den PHP-Algorithmus zum Finden der Zahl mit dem kleinsten Absolutwert in einem geordneten Array. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Frage:

Ein geordnetes Array, der Wert kann einen negativen Wert haben , oder nein, jetzt müssen wir den Wert mit dem kleinsten Absolutwert finden.

Methode 1:

Durchlaufen Sie das Array und finden Sie den absoluten Minimalwert. Die Zeitkomplexität ist O(n), n ist die Anzahl der Elemente.

Methode 2:

Binäre Suche: Da das Array geordnet ist, kann die binäre Suche verwendet werden und die zeitliche Komplexität beträgt O (logn).

Analyseschritte:

1 Wenn die erste Zahl positiv ist, bedeutet dies, dass es im gesamten Array keine negative Zahl gibt Die erste Zahl wird direkt zurückgegeben

2. Wenn die letzte Zahl eine negative Zahl ist, bedeutet dies, dass es im gesamten Array keine positive Zahl gibt und die letzte Zahl direkt zurückgegeben wird

3 . Die Array-Elemente sind positiv oder negativ, was bedeutet, dass das Element mit dem kleinsten Absolutwert in der Verbindung von positiven und negativen Zahlen liegen muss:

① Wenn a[mid]< ;0, da das Array in aufsteigender Reihenfolge vorliegt, bedeutet dies, dass die Zahl mit dem kleinsten Absolutwert nicht auf der linken Seite von a[mid] erscheint und gleichzeitig bestimmt, ob das Element a[mid+1] ist Wenn es sich um eine negative Zahl handelt, müssen Sie im Intervall auf der rechten Seite von mid-1 suchen. Wenn a[mid-1] nicht negativ ist, bedeutet dies, dass diese beiden Zahlen die positiven und negativen Schnittpunkte sind Das Array gibt den kleineren Absolutwert der beiden Zahlen zurück.

② Wenn a[mid]>0, bedeutet dies, dass die Zahl mit dem kleinsten Absolutwert nicht auf der rechten Seite von a[mid] erscheint, da das Array in aufsteigender Reihenfolge ist Bestimmen Sie gleichzeitig das Positive oder Negative des Elements a[mid-1]. Wenn es eine negative Zahl ist, bedeutet dies, dass diese beiden Zahlen die positiven und negativen Schnittpunkte im Array und den absoluten Wert der beiden Zahlen sind ist kleiner. Wenn a[mid-1] nicht negativ ist, muss es im Intervall links von mid-1 liegen.

③ Wenn a[mid] == 0, dann ist a[mid] das absolut kleinste Element.

function selectAbsMinNum(array $arr)
{
  $start = 0;
  $len = count($arr) - 1;
  if ($arr[0] > 0) { //正数数组
    return $arr[0];
  }
  if ($arr[$len] < 0) { //负数数组
    return $arr[$len];
  }
  while ($start < $len) {
    $mid = floor(($start + $len) / 2);
    if ($arr[$mid] > 0) {
      if ($arr[$mid - 1] > 0) {
        $len = $mid - 1;
      } else {
        return min($arr[$mid], -$arr[$mid - 1]);
      }
    } elseif ($arr[$mid] < 0) {
      if ($arr[$mid + 1] < 0) {
        $start = $mid + 1;
      } else {
        return min(-$arr[$mid], $arr[$mid + 1]);
      }
    } else {
      return $arr[$mid];
    }
  }
}
$sortArr = [-5, -4, -4, -4, 5, 7, 9];
echo selectAbsMinNum($sortArr), PHP_EOL;

Laufergebnis: 4

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Algorithmus zum Finden der Zahl mit dem kleinsten Absolutwert in einem geordneten Array in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!