0215. 数组中的第K个最大元素 #
- 标签:数组、堆排序
- 难度:中等
题目大意 #
描述:给定一个未排序的整数数组 nums
和一个整数 k
。
要求:返回数组中第 k
个最大的元素。
说明:
- 要求使用时间复杂度为 $O(n)$ 的算法解决此问题。
- $1 \le k \le nums.length \le 10^5$。
- $-10^4 \le nums[i] \le 10^4$。
示例:
|
|
解题思路 #
很不错的一道题,面试常考。
直接可以想到的思路是:排序后输出数组上对应第 k 位大的数。所以问题关键在于排序方法的复杂度。
冒泡排序、选择排序、插入排序时间复杂度 $O(n^2)$ 太高了,很容易超时。
可考虑堆排序、归并排序、快速排序。
这道题的要求是找到第 k
大的元素,使用归并排序只有到最后排序完毕才能返回第 k
大的数。而堆排序每次排序之后,就会确定一个元素的准确排名,同理快速排序也是如此。
思路 1:堆排序 #
升序堆排序的思路如下:
-
将无序序列构造成第
1
个大顶堆(初始堆),使得n
个元素的最大值处于序列的第1
个位置。 -
调整堆:交换序列的第
1
个元素(最大值元素)与第n
个元素的位置。将序列前n - 1
个元素组成的子序列调整成一个新的大顶堆,使得n - 1
个元素的最大值处于序列第1
个位置,从而得到第2
个最大值元素。 -
调整堆:交换子序列的第
1
个元素(最大值元素)与第n - 1
个元素的位置。将序列前n - 2
个元素组成的子序列调整成一个新的大顶堆,使得n - 2
个元素的最大值处于序列第1
个位置,从而得到第3
个最大值元素。 -
依次类推,不断交换子序列的第
1
个元素(最大值元素)与当前子序列最后一个元素位置,并将其调整成新的大顶堆。直到获取第k
个最大值元素为止。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times \log_2n)$。
- 空间复杂度:$O(1)$。
思路 2:快速排序 #
使用快速排序在每次调整时,都会确定一个元素的最终位置,且以该元素为界限,将数组分成了左右两个子数组,左子数组中的元素都比该元素小,右子树组中的元素都比该元素大。
这样,只要某次划分的元素恰好是第 k
个下标就找到了答案。并且我们只需关注第 k
个最大元素所在区间的排序情况,与第 k
个最大元素无关的区间排序都可以忽略。这样进一步减少了执行步骤。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。证明过程可参考「算法导论 9.2:期望为线性的选择算法」。
- 空间复杂度:$O(\log_2 n)$。递归使用栈空间的空间代价期望为 $O(\log_2n)$。
思路 3:借用标准库(不建议) #
提交代码中的最快代码是调用了 Python
的 sort
方法。这种做法适合在打算法竞赛的时候节省时间,日常练习不建议不建议这样做。
思路 3:代码 #
|
|
思路 3:复杂度分析 #
- 时间复杂度:$O(n \times \log_2n)$。
- 空间复杂度:$O(1)$。
思路 4:优先队列 #
- 遍历数组元素,对于挡圈元素
num
:- 如果优先队列中的元素个数小于
k
个,则将当前元素num
放入优先队列中。 - 如果优先队列中的元素个数大于等于
k
个,并且当前元素num
大于优先队列的队头元素,则弹出队头元素,并将当前元素num
插入到优先队列中。
- 如果优先队列中的元素个数小于
- 遍历完,此时优先队列的队头元素就是第K个最大元素,将其弹出并返回即可。
这里我们借助了 Python 中的 heapq
模块实现优先队列算法,这一步也可以通过手写堆的方式实现优先队列。
思路 4:代码 #
|
|
思路 4:复杂度分析 #
- 时间复杂度:$O(n \times \log_2k)$。
- 空间复杂度:$O(k)$。