Comment trouver la Kième plus grande valeur d'un tableau à l'aide de l'algorithme PHP

Dans le développement PHP, il est souvent nécessaire de trier et de rechercher des tableaux et d'autres opérations. Trouver la Kième plus grande valeur dans un tableau est également un problème courant. Cet article présentera plusieurs algorithmes PHP pour atteindre la Kème plus grande valeur d'un tableau.

1. Méthode de tri par bulles

La méthode de tri par bulles est un algorithme de tri simple et facile à comprendre. Son idée de base est de comparer les éléments adjacents. Si l'élément précédent est plus grand que l'élément suivant, échangez leurs positions. La complexité temporelle de cette méthode est O(n^2).

Le code d'implémentation est le suivant :

function bubbleSort($arr) {
  $len = count($arr);
  for ($i=0; $i<$len-1; $i++) {
    for ($j=0; $j<$len-$i-1; $j++) {
      if ($arr[$j] > $arr[$j+1]) {
        $temp = $arr[$j];
        $arr[$j] = $arr[$j+1];
        $arr[$j+1] = $temp;
      }
    }
  }
  return $arr;
}

function findKthLargest($nums, $k) {
  $nums = bubbleSort($nums);
  $len = count($nums);
  return $nums[$len-$k];
}

2. Méthode de tri rapide

La méthode de tri rapide est un algorithme de tri efficace. Son idée de base est de sélectionner un élément de référence dans le tableau, de placer les éléments plus petits que l'élément de référence. à gauche et placez les éléments plus grands que l'élément de référence à gauche. Les éléments sont placés à droite et les plages de gauche et de droite sont triées de manière récursive. La complexité temporelle de cette méthode est O(nlogn).

Le code d'implémentation est le suivant :

function quickSort($arr) {
  $len = count($arr);
  if ($len <= 1) {
    return $arr;
  }
  $pivot = $arr[0];
  $left = [];
  $right = [];
  for ($i=1; $i<$len; $i++) {
    if ($arr[$i] < $pivot) {
      $left[] = $arr[$i];
    } else {
      $right[] = $arr[$i];
    }
  }
  return array_merge(quickSort($left), [$pivot], quickSort($right));
}

function findKthLargest($nums, $k) {
  $nums = quickSort($nums);
  $len = count($nums);
  return $nums[$len-$k];
}

3. Méthode de tri par tas

La méthode de tri par tas est un algorithme de tri basé sur la structure du tas. Son idée de base est de construire une séquence non ordonnée dans un tas et d'en retirer séquentiellement le maximum. valeur en haut du tas, puis reconstruisez la séquence non ordonnée restante en un tas, et ainsi de suite jusqu'à ce qu'elle soit triée. La complexité temporelle de cette méthode est O(nlogn).

Le code d'implémentation est le suivant :

function heapSort($arr) {
  $len = count($arr);
  for ($i=floor($len/2)-1; $i>=0; $i--) {
    adjustHeap($arr, $i, $len);
  }
  for ($j=$len-1; $j>0; $j--) {
    swap($arr, 0, $j);
    adjustHeap($arr, 0, $j);
  }
  return $arr;
}

function adjustHeap(&$arr, $i, $len) {
  $temp = $arr[$i];
  for ($k=$i*2+1; $k<$len; $k=$k*2+1) {
    if ($k+1 < $len && $arr[$k] < $arr[$k+1]) {
      $k++;
    }
    if ($arr[$k] > $temp) {
      $arr[$i] = $arr[$k];
      $i = $k;
    } else {
      break;
    }
  }
  $arr[$i] = $temp;
}

function swap(&$arr, $i, $j) {
  $temp = $arr[$i];
  $arr[$i] = $arr[$j];
  $arr[$j] = $temp;
}

function findKthLargest($nums, $k) {
  $nums = heapSort($nums);
  $len = count($nums);
  return $nums[$len-$k];
}

Les trois algorithmes PHP courants ci-dessus permettent de résoudre la Kième plus grande valeur d'un tableau. Dans les applications pratiques, nous devons choisir un algorithme approprié basé sur la situation réelle pour garantir l'efficacité.

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!