给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildMaxHeap(nums, heapSize);
for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
swap(nums, 0, i);
heapSize--;
heapify(nums, 0, heapSize);
}
return nums[0];
}
public void buildMaxHeap(int[] nums, int heapSize) {
for (int i = heapSize / 2 - 1; i >= 0; i--) {
heapify(nums, i, heapSize);
}
}
public void heapify(int[] nums, int i, int heapSize) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i;
if (left < heapSize && nums[left] > nums[largest]) {
largest = left;
}
if (right < heapSize && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums, largest, i);
heapify(nums, largest, heapSize);
}
}
public void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
可以维护一个大根堆，需要第几个最大的值，就删掉前几个更大的值就好了。
用一个数组创建一个大根堆
先把这个数组当作是一个满二叉树，我们不需要调整这个二叉树的叶子结点，因为一个满二叉树的叶子结点比内部节点多 1 个，设这个满二叉树的节点数为 n ，所以只需要从第 n / 2 - 1 开始就可以了，这是最后一个内部节点。然后进行循环就好了。
维护这个大根堆
有一个当前的节点，根据性质，这个节点的左子节点是 i * 2 + 1, 这个节点的右子节点是 i * 2 + 2, 从这三个节点里选出最大的，作为当前的最大点，然后再依次向下即可。
删除节点
当我们的大根堆维护完了之后，那么就只需要执行对应的几次删除节点操作即可，把最大的和最小的进行替换，同时维护堆大小，然后再维护一次即可，最后根就是答案。