categories: leetcode

215.png

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1: 输入: ``` [3,2,1,5,6,4] 和

  1.  k = 2
  2. **输出:** 5**示例 2:**
  3. **输入:**

[3,2,3,1,2,4,5,5,6] 和

  1.  k = 4
  2. **输出:** 4**说明:**<br />你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
  3. <a name="36967e2c"></a>
  4. ## 参考代码
  6. ```java
  7. class Solution {
  8.    public static int findKthLargest(int[] nums, int k) {
  9.         PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
  10.        for(int num :nums) {
  11.            priorityQueue.add(num);
  12.            if(priorityQueue.size() > k) {
  13.                priorityQueue.poll();
  14.            }
  15.        }
  16.        return priorityQueue.peek();
  17.    }
  18. }

思路及总结

主要思路就是通过各种方式将数组从大到小有序化（各种排序算法，由大到小更容易判断k的位置），利用优先队列PriorityQueue从大到小排列，想象一个二叉树，在第k个之后的内容没有意义，在添加进去的同时便可以删去，减少了调用add()函数的时间，将所有数添加完毕，处于peek的数既是数组中第k个最大元素。

参考

https://www.kancloud.cn/maliming/leetcode/844880