题目
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
提示：
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答一
对于 PHP 来说这道题是非常简单的，因为 PHP 中大量这样的数组函数，可以很方便的对数组进行排序。这里我们只需要直接使用 sort() 函数就可以了。
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function findKthLargest($nums, $k) {
rsort($nums);
return $nums[$k-1];
}
}
执行用时：24 ms, 在所有 PHP 提交中击败了49.48%的用户
内存消耗：19.5 MB, 在所有 PHP 提交中击败了83.51%的用户
通过测试用例：32 / 32
解答二
自己编写归并排序
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function findKthLargest($nums, $k) {
$arr = $this->mergeSort($nums);
return $arr[$k-1];
}
/** 归并排序 */
function mergeSort($nums) {
$len = count($nums);
if ($len < 2) return $nums;
$m = intval($len / 2);
$left = $this->mergeSort(array_slice($nums, 0, $m));
$right = $this->mergeSort(array_slice($nums, $m, $len-$m));
$arr = [];
while (count($left) && count($right)) {
if ($left[0] >= $right[0])
$arr[] = array_shift($left);
else
$arr[] = array_shift($right);
}
while (count($left))
$arr[] = array_shift($left);
while (count($right))
$arr[] = array_shift($right);
return $arr;
}
}
执行用时：200 ms, 在所有 PHP 提交中击败了22.81%的用户
内存消耗：20.1 MB, 在所有 PHP 提交中击败了14.91%的用户
通过测试用例：32 / 32
解答三
自己编写快排
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function findKthLargest($nums, $k) {
$this->quickSort($nums, 0, count($nums)-1);
return $nums[$k-1];
}
/** 快速排序 */
function quickSort(array &$nums, int $a, int $b) {
if ($a >= $b) return;
$i = $a;
$j = $b;
$mi = true;
while ($i < $j) {
if ($nums[$i] < $nums[$j]) {
[$nums[$i], $nums[$j]] = [$nums[$j], $nums[$i]];
$mi = !$mi;
}
$mi ? $j-- : $i++;
}
$this->quickSort($nums, $a, $i-1);
$this->quickSort($nums, $i+1, $b);
}
}
执行用时：824 ms, 在所有 PHP 提交中击败了16.67%的用户
内存消耗：21.8 MB, 在所有 PHP 提交中击败了11.40%的用户
通过测试用例：32 / 32
解答四 ✅
快排，但是只排 k 范围内的部分，并且在快排中选择中点数据时使用 rand() 函数，尽可能避免最坏的 O(n²) 情况出现。
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function findKthLargest($nums, $k) {
return $this->quickSort($nums, 0, count($nums)-1, $k-1);
}
/** 快速排序 */
function quickSort(array &$nums, int $a, int $b, $k) {
if ($a >= $b) return $nums[$a];
$r = rand($a, $b);
[$nums[$a], $nums[$r]] = [$nums[$r], $nums[$a]];
$j = $a;
$v = $nums[$a];
for ($i = $a+1; $i <= $b; $i++) {
if ($nums[$i] > $v) {
$j++;
[$nums[$i], $nums[$j]] = [$nums[$j], $nums[$i]];
}
}
[$nums[$a], $nums[$j]] = [$nums[$j], $nums[$a]];
if ($k == $j) {
return $nums[$j];
} else if ($k < $j) {
return $this->quickSort($nums, $a, $j-1, $k);
} else {
return $this->quickSort($nums, $j+1, $b, $k);
}
}
}
执行用时：12 ms, 在所有 PHP 提交中击败了99.12%的用户
内存消耗：19.9 MB, 在所有 PHP 提交中击败了28.07%的用户
通过测试用例：32 / 32
解答五
采用堆排序，建立大根堆，依次取大根堆的根节点 k 次就可以了
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function findKthLargest($nums, $k) {
$end = count($nums) - 1;
// 初始化大根堆
$this->initMaxHeap($nums, $end);
// 循环至取出 k
$max = null;
while ($k-- > 0) {
$max = $nums[0];
$nums[0] = $nums[$end];
$this->heapify($nums, --$end, 0);
}
return $max;
}
/** 初始化大根堆 */
function initMaxHeap(array &$nums, int $end) {
if ($end < 1) return;
for ($parent = intval(($end-1)/2); $parent >= 0; $parent--) {
$child = $parent * 2 + 1;
$child+1 <= $end and $nums[$child+1] > $nums[$child] and $child++;
if ($nums[$child] > $nums[$parent]) {
[$nums[$parent], $nums[$child]] = [$nums[$child], $nums[$parent]];
$this->heapify($nums, $end, $child);
}
}
}
/** 堆化整理分支 */
function heapify(array &$nums, int $end, int $parent) {
for (; $parent * 2 + 1 <= $end; $parent = $child) {
$child = $parent * 2 + 1;
$child+1 <= $end and $nums[$child+1] > $nums[$child] and $child++;
if ($nums[$child] <= $nums[$parent]) break;
[$nums[$parent], $nums[$child]] = [$nums[$child], $nums[$parent]];
}
}
}
执行用时：28 ms, 在所有 PHP 提交中击败了44.74%的用户
内存消耗：19.7 MB, 在所有 PHP 提交中击败了52.63%的用户
通过测试用例：32 / 32