找到数组中第K大的元素，N远大于K
注意事项
你可以改变数组中元素的位置
样例
在数组 [9,3,2,4,8] 中, 第三大的元素是 4。
在数组 [1,2,3,4,5] 中, 第一大 的元素是 5，第二大 的元素是 4，第三大 的元素是3等等。
思路
用 PriorityQueue 来实现，PriorityQueue 的大小始终保持在 K 个，遍历所有数，和 PriorityQueue 中最小数比较，如果大于最小数，将最小数抛出 PriorityQueue，当前数加入 PriorityQueue，PriorityQueue 内部重新排出最小数，进入下一轮比较，等所有数遍历完了，PriorityQueue 中最小数就是第K大的数。
区别
首先要强调下快排，快速排序是一种不稳定算法，最好情况下时间复杂度为 O(NlogN)，最坏情况时间复杂度为 O(N^2)
而 quickSelect 是基于快排的另一种算法在 K 和 N 接近时会达到接近 O(N) 的时间复杂度，但如果 N >> K 时，快排每次切分都不均匀，可能会使 quickSelect 算法时间复杂度无法达到 O(N)，最坏可能 O(N^2)
本题和 5.第k大元素 的区别在于上一题中，K 和 N 在一个数量级，用快排来解题可达到时间复杂度接近 O(N) ，而本题在 K 比较小(N 远大于 K)的情况下，优先队列可以稳定实现时间复杂度为 O(NlogK) 的算法
O(NlogK) 在数量级上是大于 O(N) 的，不管 K 取多少，当 K << N 时，快速选择 O(N) < 优先队列 O(NlogK) < 快速排序平均 O(NlogN) < 快速排序最坏 O(N^2)
代码
class Solution {
/**
* @param nums an integer unsorted array
* @param k an integer from 1 to n
* @return the kth largest element
*/
public int kthLargestElement2(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);
for (int num : nums) {
q.offer(num);
if (q.size() > k) {
q.poll();
}
}
return q.peek();
}
}
PriorityQueue补充
PriorityQueue 在用 PriorityQueue() 作为构造函数时，默认容量是 11
PriorityQueue(int initialCapacity) 作为构造函数，会用 initialCapacity 作为默认容量。
优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组的大小。它总是至少与队列的大小相同。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。绝大部分的容器都是无界的。
