215. Kth Largest Element in an Array (Medium)
https://leetcode.com/problems/kth-largest-element-in-an-array/
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.
Solutions
class Solution {
public int findKthLargest(int[] nums, int k) {
heapSort(nums, k);
return nums[nums.length - k];
}
private void heapSort(int[] nums, int k) {
int len = nums.length;
for (int i = 1; i <= k; i++) {
maxHeapify(nums, len - i);
swap(nums, 0, len - i);
}
}
private void maxHeapify(int[] nums, int n) {
// n is index and pay close attention to the difference of index and length.
// Assume length is 2, the parent slot should be (2 - 1) / 2 = 0,
// otherwise if parent being 1, left = 2, right = 3, both exceed the boundary of nums
for (int i = n / 2; i >= 0; i--) {
// parent node index
int pid = i;
// left child index
int left = pid * 2;
// right child index
int right = pid * 2 + 1;
// no right child node
if (right > n) {
right = left;
}
if (nums[left] > nums[pid]) {
swap(nums, left, pid);
}
if (nums[right] > nums[pid]) {
swap(nums, right, pid);
}
}
}
private void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
}