215. 数组中的第K个最大元素

题目

给定整数数组 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

本作品采用《CC 协议》，转载必须注明作者和本文链接