PHPアルゴリズムを使用して配列内のK番目に大きい値を見つける方法

PHP 開発では、配列の並べ替えや検索、その他の操作が必要になることがよくあります。配列内で K 番目に大きい値を見つけることもよくある問題です。この記事では、配列内の K 番目に大きい値を取得するためのいくつかの PHP アルゴリズムを紹介します。

1. バブルソート法

バブルソート法は、隣接する要素を比較するというシンプルでわかりやすいソートアルゴリズムです。 element 要素の位置を交換します。このメソッドの時間計算量は O(n^2) です。

実装コードは以下の通り:

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. クイックソート法

クイックソート法は効率的なソートアルゴリズムであり、基本的な考え方は以下からベンチマーク要素を選択することである。シーケンス。 、基準要素より小さい要素を左側に、基準要素より大きい要素を右側に配置し、左右の間隔を再帰的に並べ替えます。このメソッドの時間計算量は O(nlogn) です。

実装コードは次のとおりです:

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. ヒープソート方式

ヒープソート方式は、ヒープ構造に基づいたソートアルゴリズムです。順序のないシーケンスをヒープに構築し、連続してヒープの先頭の最大値を取り出し、残りの順序のないシーケンスをヒープに再構築するなど、順序が整うまで繰り返します。このメソッドの時間計算量は O(nlogn) です。

実装コードは次のとおりです:

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

上記は、配列内の K 番目に大きい値を解決するための 3 つの一般的な PHP アルゴリズムです。実際のアプリケーションでは、効率を確保するために実際の状況に基づいて適切なアルゴリズムを選択する必要があります。

以上がPHPアルゴリズムを使用して配列内のK番目に大きい値を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。