How to find the Kth largest value in an array using PHP algorithm

In PHP development, it is often necessary to sort and search arrays and other operations. Finding the Kth largest value in an array is also a common problem. This article will introduce several PHP algorithms to achieve the Kth largest value in an array.

1. Bubble sorting method

Bubble sorting method is a simple and easy-to-understand sorting algorithm. Its basic idea is to compare adjacent elements. If the previous element is larger than the following element elements, swap their positions. The time complexity of this method is O(n^2).

The implementation code is as follows:

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. Quick sorting method

Quick sorting method is an efficient sorting algorithm. Its basic idea is to select a benchmark element from the sequence. , place elements smaller than the reference element on the left, elements greater than the reference element on the right, and then recursively sort the left and right intervals. The time complexity of this method is O(nlogn).

The implementation code is as follows:

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. Heap sorting method

The heap sorting method is a sorting algorithm based on the heap structure. Its basic idea is to construct an unordered sequence into a heap, and successively take out the maximum value at the top of the heap, and then reconstruct the remaining unordered sequence into a heap, and so on until it is in order. The time complexity of this method is O(nlogn).

The implementation code is as follows:

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

The above are three common PHP algorithms for solving the Kth largest value in an array. In practical applications, we need to choose an appropriate algorithm based on the actual situation to ensure efficiency.

The above is the detailed content of How to find the Kth largest value in an array using PHP algorithm. For more information, please follow other related articles on the PHP Chinese website!