Bagaimana untuk mencari nilai terbesar Kth dalam tatasusunan menggunakan algoritma PHP

Dalam pembangunan PHP, selalunya perlu mengisih dan mencari tatasusunan dan operasi lain. Mencari nilai Kth terbesar dalam tatasusunan juga merupakan masalah biasa. Artikel ini akan memperkenalkan beberapa algoritma PHP untuk mencapai nilai terbesar Kth dalam tatasusunan.

1. Kaedah pengisihan gelembung

Kaedah pengisihan buih ialah algoritma pengisihan yang mudah dan mudah difahami elemen elemen, menukar kedudukan mereka. Kerumitan masa kaedah ini ialah O(n^2).

Kod pelaksanaan adalah seperti berikut:

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 Kaedah pengisihan pantas

Kaedah pengisihan pantas ialah algoritma pengisihan yang cekap ialah memilih satu daripadanya jujukan. Untuk unsur asas, letakkan unsur yang lebih kecil daripada unsur asas di sebelah kiri, dan unsur yang lebih besar daripada unsur asas di sebelah kanan, dan kemudian susun secara rekursif selang kiri dan kanan. Kerumitan masa kaedah ini ialah O(nlogn).

Kod pelaksanaan adalah seperti berikut:

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. Kaedah pengisihan timbunan

Kaedah pengisihan timbunan ialah algoritma pengisihan berdasarkan idea asasnya untuk mengisih yang tidak tersusun Jujukan dibina menjadi timbunan, dan nilai maksimum di bahagian atas timbunan dikeluarkan secara bergilir-gilir, dan jujukan tidak tertib yang selebihnya dibina semula menjadi timbunan, dan seterusnya sehingga ia teratur. Kerumitan masa kaedah ini ialah O(nlogn).

Kod pelaksanaan adalah seperti berikut:

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

Di atas ialah tiga algoritma PHP biasa untuk menyelesaikan nilai terbesar Kth dalam tatasusunan. Dalam aplikasi praktikal, kita perlu memilih algoritma yang sesuai berdasarkan situasi sebenar untuk memastikan kecekapan.

Atas ialah kandungan terperinci Bagaimana untuk mencari nilai terbesar Kth dalam tatasusunan menggunakan algoritma PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!