LeetCode 第215题 Kth Largest Element in an Array 【堆】Java

原题地址:https://leetcode.com/problems/kth-largest-element-in-an-array/

寻找一个乱序数组中第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

注意:你可以认为k永远合法,1 ≤ k ≤ 数组的长度。

这道题我们有两个思路。

第一个很简单,两行结束,先排序,然后再输出第k为的元素即可。代码如下:

第二种其实也不难,首先构建一个最大堆,然后再输出k个元素,第k个元素就是我们的目标。代码如下:(最大堆代码参见前文

代码地址:https://github.com/tinyfool/leetcode/tree/master/src/p0215

也请参阅《Leetcode专题 堆结构和堆排序》,文章介绍了堆和堆排序,以及最大堆的实现。

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据