# LeetCode 215. Kth Largest Element in an Array

@(LeetCode)

问题描述



找出数组中第 k 个最大的数。注意是数组排序后第 k 大的数，而不是去重后的第 k 大的数。



栗 1：

输入：[3,2,1,5,6,4], k = 2
输出：5

解释：
排序后：[1,2,3,4,5,6]，倒数第 2 个数为 5。



栗 2：

输入：[3,2,3,1,2,4,5,5,6], k = 4
输出：4

解释：
排序后：[1,2,2,3,3,4,5,5,6]，倒数第 4 个数为 4。



注意：

• 假定 k 一定有效，范围是 1 ≤ k ≤ array's length。



想看英文原文的戳这里。



解题思路



首先来说明一下第 k 大的数定义，即将数组从小到大排序后，从它开始到数组末尾，总共有 k 个数。



解法 1



最容易想到的思路：将数组从小到大排序后，取倒数第 k 个数。



但显然，这道题考察的点肯定不是排序这种简单的方式。



解法 2



我们在学排序算法时，有一种方法是快排。其中有一个关键步骤叫做 partiton，即分区。也就是任意选定一个数，将小于它的数放在它前面，将大于等于它的数放在它后面，返回该数的位置，我们称之为基准点。这样，基准点就将待排序列分为了左右两部分。



分区后，从基准点开始，都是大于等于它的数。而我们知道基准点的位置，从而可以推算基准点是第几大的数。



因为我们只需要计算出第 k 大的数，并没有排序要求，所以完全可以借鉴分区的思路。



假设 len = 从基准点开始到数组末尾元素的总个数，则基准点是第 len 大的数。



• 若 len == k，那么基准点刚好是第 k 大的数。

• 若 len < k，那么说明结果肯定在左边，需要往基准点的左边找，且 k = k - len。这里需要注意更新 k 值。

• 若 len > k，那么说明结果肯定在右边，需要往基准点的右边找，k 不变。



点击查看具体实现。



解法 3



思路跟解法 2 有些相似。同样是选定一个基准点，将小于它的数放到它前面，大于等于它的数放到后面，但不使用分区算法。相对来说，更好理解一些，但需要额外的空间。



简单来说，就是将小于它的数放到数组 leftPart 中，将大于等于它的数放到另一个数组 rightPart 中，自身不放入。



假设 k = rightPart.length + 1。



• 若 len == k，那么基准点即为结果。

• 若 len < k，那么在 leftPart 中找，同样 k = k - len。

• 若 len > k，那么在 rightPart 中找，k 不变。



点击查看具体实现。