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<Integer> pq = new PriorityQueue<>(); for (int num : nums) { pq.offer(num); if (pq.size() > k) { pq.poll(); } } return pq.poll(); } }
[LC] 215. Kth Largest Element in an Array
原文：https://www.cnblogs.com/xuanlu/p/11879712.html