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.
For example,
Given[3,2,1,5,6,4]and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
2. Implementation
(1) Quick Select
class Solution {
public int findKthLargest(int[] nums, int k) {
return getKthNum(nums, 0, nums.length - 1, k - 1);
}
public int getKthNum(int[] nums, int start, int end, int k) {
int pivot = partition(nums, start, end);
if (pivot < k) {
return getKthNum(nums, pivot + 1, end, k);
}
else if (pivot > k) {
return getKthNum(nums, start, pivot - 1, k);
}
else {
return nums[pivot];
}
}
public int partition(int[] nums, int start, int end) {
int mid = start + (end - start) / 2;
swap(nums, mid, end);
for (int i = start; i < end; i++) {
if (nums[i] > nums[end]) {
swap(nums, i, start);
++start;
}
}
swap(nums, start, end);
return start;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
(2) Heap
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.remove();
}
}
return minHeap.peek();
}
}