一、什么是TopK问题？
📝TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
二、解决思路是什么？
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，
🍑有小伙伴可能就会这样干：比如要求数组中前k个最大的元素，那么就把该数组建立为大根堆（此时堆顶元素不就是当前数组中最大的吗）
🍑然后不就可以不断的弹出当前堆顶元素，同时不断的更新堆顶以及保证当前堆一直是大根堆。像这样我们所弹出的K个元素不就是数组前k个最大元素吗？
于是我们写出来这样的代码：
/** * topK问题，找出数组中最大的k个元素， 但这不是最优的解决方案 * 时间复杂度：O(N * logn), 想一下他的空间复杂度的是多少，是O(n)吗？ * @param array * @return 前k个元素所组成的数组 */ public static int[] topK1(int[] array, int k) { IntCmp intCmp = new IntCmp(); // 自定义的比较器，用来实现大根堆（因为PriorityQueue的排序方法默认实现小根堆） // 创建具有默认初始容量的 PriorityQueue ，并根据指定的比较器对其元素进行排序。 PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(intCmp); for (int i = 0; i < array.length; i++) { priorityQueue.offer(array[i]); // 每插入一个元素就要向上调整一次，时间复杂度：n * logn } // 程序走到这里我们已经构建了一个大根堆 int[] ret = new int[k]; for (int i = 0; i < k; i++) { ret[i] = priorityQueue.poll(); // 每弹出一个堆顶元素就要向下调整一次，时间复杂度：n * logn } return ret; } // 自定义了一个比较器对象，完成大根堆的构建 class IntCmp implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }
这样做当然可以但不是最优的解决方法 🤔
最优的解决思路如下：
基本思路如下：
1. 用数据集合中前K个元素来建堆
求前k个最大的元素，则建小堆
求前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
三、代码实现
import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; public class Test1 { /** * topK问题，最优解法 * @return 堆中前k个最大的元素所组成的数组 */ public static int[] topK(int[] array, int k) { // 要求堆中前k个最大元素，先将数组中前k个元素建成小根堆（如果要求堆中前k个最小元素，先将数组中前k个元素建成大根堆，正好是反过来的） // 创建一个PriorityQueue ，具有默认的初始容量（11），根据它们的natural ordering对其元素进行排序 。默认的排序方法建成的是小根堆） PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); for (int i = 0; i < k; i++) { priorityQueue.offer(array[i]); } // 遍历剩下的array.length - k个元素，从数组的第k + 1个元素开始，剩下的每个元素都和当前堆顶元素进行比较 // 如果当前i下标的元素比堆顶元素大，就删除堆顶元素，并把i下标的元素放到堆中 for (int i = k; i < array.length; ++i) { if (array[i] > priorityQueue.peek()) { priorityQueue.poll(); priorityQueue.offer(array[i]); } } int[] ret = new int[k]; for (int i = 0; i < k; i++) { ret[i] = priorityQueue.poll(); } return ret; } // 主函数，程序的入口 public static void main(String[] args) { int[] a = {23, 42, 23, 32, 12}; int[] ret = topK(a,2); System.out.println("数组中前两个最大的元素是："+ Arrays.toString(ret)); } }
四、OJ实战演练
思路：直接套用我们刚才的TopK求解方法就好
🌰代码实现
class Solution { class IntCmp implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; // 构建大根堆 } } public int[] smallestK(int[] array, int k) { if (k == 0) return new int[0]; // 要求堆中前k个最小元素，先将数组中前k个元素建成大根堆，正好是反过来的 // 创建一个PriorityQueue ，具有默认的初始容量（11），根据它们的natural ordering对其元素进行排序 。默认的排序方法建成的是小根堆） IntCmp intCmp = new IntCmp(); PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(intCmp); for (int i = 0; i < k; i++) { priorityQueue.offer(array[i]); } // 遍历剩下的array.length - k个元素，从数组的第k + 1个元素开始，剩下的每个元素都和当前堆顶元素进行比较 // 如果当前i下标的元素比堆顶元素小，就删除堆顶元素，并把i下标的元素放到堆中 for (int i = k; i < array.length; ++i) { if (array[i] < priorityQueue.peek()) { priorityQueue.poll(); priorityQueue.offer(array[i]); } } int[] ret = new int[k]; for (int i = 0; i < k; i++) { ret[i] = priorityQueue.poll(); } return ret; } }
五、TopK问题扩展：求数组中第k大的元素
思路：
在求堆中前K个最大元素的过程中，最后得到的堆顶元素就是第K大的元素
🌰代码实现
// 获取当前数组中第K大的元素 public static int getK(int[] array, int k) { // 要求堆中前k个最大元素，先将数组中前k个元素建成小根堆（如果要求堆中前k个最小元素，先将数组中前k个元素建成大根堆，正好是反过来的） PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); for (int i = 0; i < k; i++) { priorityQueue.offer(array[i]); } // 遍历剩下的array.length - k个元素，从数组的第k + 1个元素开始，剩下的每个元素都和当前堆顶元素进行比较 // 如果当前i下标的元素比堆顶元素大，就删除堆顶元素，并把i下标的元素放到堆中 for (int i = k; i < array.length; ++i) { if (array[i] > priorityQueue.peek()) { priorityQueue.poll(); priorityQueue.offer(array[i]); } } // 程序运行到了这里，我们的优先级队列里（堆中）存放的就是堆中前k个最大的元素，此时堆顶元素就是第k大的元素 return priorityQueue.peek(); }
