优先队列的思路是很朴素的。由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：
如果当前堆不满，直接添加；
堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新遍历到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。
说明：这里最合适的操作其实是 replace()，即直接把新读进来的元素放在堆顶，然后执行下沉（siftDown()）操作。Java 当中的 PriorityQueue 没有提供这个操作，只好先 poll() 再 offer()。
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a - b);
for (int i = 0; i < k; i++) {
minHeap.offer(nums[i]);
}
for (int i = k; i < len; ++i) {
Integer topElement = minHeap.peek();
if (nums[i] > topElement) {
minHeap.poll();
minHeap.offer(nums[i]);
}
}
return minHeap.peek();
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
// 使用小顶堆
PriorityQueue pq = new PriorityQueue<>(k);
for (int num : nums) {
if (pq.size() < k) {
pq.offer(num);
} else if (pq.peek() < num) {
pq.poll();
pq.offer(num);
}
}
return pq.peek();
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue pq = new PriorityQueue<>((a, b) -> b - a);
for (Integer num : nums) {
pq.add(num);
}
for (int i = 0; i < k - 1; i++) {
pq.remove();
}
return pq.peek();
}
}
使用数组建堆
class Solution {
public int findKthLargest(int[] nums, int k) {
// 使用数组构建小顶堆
int[] top = new int[k];
// 将 nums 数组中的前 k 个元素取出来
for (int i = 0; i < k; i++) {
top[i] = nums[i];
}
// 先建堆，然后依次比较剩余元素与堆顶元素的大小，比堆顶大的，说明它应该在堆中出现，则用它来替换掉堆顶元素，然后沉降。
buildHeap(top);
for (int j = k; j < nums.length; j++) {
int temp = top[0];
if (temp < nums[j]) {
setTop(top, nums[j]);
}
}
return top[0];
}
// 建堆
public void buildHeap(int[] nums) {
// 最后一个节点
int lastNode = nums.length - 1;
// 找到最后一个节点的父节点
int startHeapify = (lastNode - 1) / 2;
for (int i = startHeapify; i >= 0; i--) {
// 不断调整建堆
heapify(nums, i, nums.length);
}
}
// 不断调整小顶堆
public void heapify(int[] nums, int index, int length) {
// 左右子节点
int left = (index << 1) + 1;
int right = (index << 1) + 2;
// 假定当前节点最小
int min = index;
// 比较左右子节点找到最小值
if (left < length && nums[left] < nums[min]) {
min = left;
}
if (right < length && nums[right] < nums[min]) {
min = right;
}
// 如果不相等就需要交换
if (min != index) {
swap(nums, min, index);
// 递归调用
heapify(nums, min, length);
}
}
// 交换数组元素
public void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
// 将堆顶元素进行更换，继续进行沉降
public void setTop(int[] nums, int top) {
nums[0] = top;
heapify(nums, 0, nums.length);
}
}
快排
class Solution {
public int findKthLargest(int[] nums, int k) {
return getTopK(nums, k);
}
// 分治
public int partition(int[] nums, int low, int high) {
int pivot = nums[low];
while (low < high) {
while (low < high && nums[high] <= pivot) {
high--;
}
nums[low] = nums[high];
while (low < high && nums[low] >= pivot) {
low++;
}
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}
// 获得 Kth 的数
public int getTopK(int[] nums, int k) {
int low = 0;
int high = nums.length - 1;
// 不断调整分治的位置，直到 position = k - 1
while (true) {
int index = partition(nums, low, high);
if (index == k - 1) {
return nums[index];
}
else if (index < k - 1) {
low = index + 1;
}
else {
high = index - 1;
}
}
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
return getTopK(nums, k);
}
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private static int partition(int[] nums, int l, int r) {
// 取分界点
int x = nums[l];
int i = l + 1, j = r;
while (true) {
while (i < r && nums[i] > x) i++;
while (j > l && nums[j] < x) j--;
if (i >= j) break;
swap(nums, i, j);
i++;
j--;
}
swap(nums, l, j);
return j;
}
// 获得 Kth 的数
private static int getTopK(int[] nums, int k) {
int l = 0, r = nums.length - 1;
// 不断调整分治的位置，直到 position = k - 1
int index = partition(nums, l, r);
while (index != k - 1) {
if (index > k - 1) {
r = index - 1;
index = partition(nums, l, r);
} else if (index < k - 1) {
l = index + 1;
index = partition(nums, l, r);
}
}
return nums[index];
}
}
