Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution 1:

Time: O(NlgN)

class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}

Solution 2:

Time: O(Nlgk)

class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
PriorityQueue pq = new PriorityQueue<>();
for (int num : nums) {
pq.offer(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.poll();
}
}