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:
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int val : nums) { if (pq.size() < k) { pq.offer(val); } else if (val > pq.peek()) { pq.poll(); pq.offer(val); } } int result = pq.poll(); return result; } }
class Solution { public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, k); }
private int quickSelect(int[] nums, int left, int right, int k) { int pivot = left; for (int i = left; i < right; i ++) { if (nums[i] <= nums[right]) { swap(nums, pivot ++, i); } } swap(nums, pivot, right); int count = right - pivot + 1; if (count == k) { return nums[pivot]; } else if (count < k) { return quickSelect(nums, left, pivot - 1, k - count); } else { return quickSelect(nums, pivot + 1, right, k); } }
private void swap(int[] nums, int x, int y) { int temp = nums[x]; nums[x] = nums[y]; nums[y] = temp; } }