题目大意：
数组中的第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 说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=215
解题思路分析：
解法一：排序
先说一种最简单的思路，我们将数组升序排序，然后取得数组倒数第k个数即可。
实现代码：
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
} 本解法执行时间为1ms。
Runtime: 1 ms, faster than 99.47% of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 41.3 MB, less than 5.18% of Java online submissions for Kth Largest Element in an Array.
解法二：Heap
相对于解法一稍微复杂一些，但也非常好理解。我们循环数组中的每一个数字，然后使用一个PriorityQueue来保存遍历到的数，当 PriorityQueue 中的元素个数大于k时，我们从Queue中poll出一个元素，该元素应该是Queue中最小的那个。直到遍历完所有数字， PriorityQueue 中保存的应该是数组中前k大的所有数字，并且PriorityQueue中首元素应该是其中最小一个，也就是全局第k大的数字。
实现代码：
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int n : nums){
q.offer(n);
if(q.size()>k) q.poll();
}
return q.poll();
} 本题解法执行时间为4ms。
Runtime: 4 ms, faster than 70.55% of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 40.8 MB, less than 5.18% of Java online submissions for Kth Largest Element in an Array.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-215-kth-largest-element-in-an-array-解题思路分析/