算法面试必问：Top K问题浅析
最近为了扩大团队规模，一直时刻保持脉脉上动态的更新，希望能认识一些新朋友新伙伴。发现脉脉确实挺有意思的哈，有人吐槽职场，有人招聘，有人分享面经，我今天看到有人发了个动态说面试被问Top K问题，忘记怎么做了，答得不是很好。
可能最近刷题刷多了，说时迟那时快，我本能地开始在脑海里回顾Top K该怎么解答。
那什么是Top K问题？
不是所有的场景都需要我们找到最大的，最小的，或者平均的元素，在很多情况下，我们会遇到在n个元素中找到第k大，第k小，第k快诸如此类的问题。这样的问题我们统称为Top K问题。
举个栗子？
我们先来看这么一道题：给定一个未排序的数组，返回其中前K大元素。
示例1:
输入: [3, 1, 5, 12, 2, 11], K = 3
输出: [5, 12, 11]
示例2:
输入: [5, 12, 11, -1, 12], K = 3
输出: [12, 11, 12]
很简短很直白，相信我们大家每次做算法题都是习惯性地暴力循环，先把性能啊复杂度啊之类的东西抛之脑后。那么一个常见的做法就是我们对这个数组进行排序，然后返回第K大元素。这样的解法时间复杂度需要 O(N*logN)，这是排序所需要的。那可以做的更好吗？这肯定不是面试官想要的答案，要真是这种程度的答案，那这应该是给大一新生的课后作业。?
答案是可以，我之前在双堆问题里面也说过，在一堆数据中追踪前几个符合条件的数据用堆最快。我们来看看用堆我们能不能得到一个更好的方案？
如果我们遍历这个数组，并且在堆中保存最大的K个元素，一旦我们遇到一个比堆中最小元素大的元素，我们要做两件事：
- 从堆中移除最小的那个元素
- 把这个更大的元素插入到堆中
这样我们就可以保证堆中保存的是我们到目前为止遇到的最大的K个元素。重复地在一堆数据中找到最小的元素最有效率的方式就是使用最小堆。在最小堆里面拿最小的元素时间复杂度只有O(1)，因为最小元素都在最顶部。从堆中删除一个元素要O(N)，因为删除后堆需要重新确定元素。
我们用示例1来盘一下我们的解法分为哪几步：
- 向最小堆中插入K个元素
- 插入后，堆有三个元素
[3, 1, 5]，1因为是最小元素所以在根部 - 遍历数组中剩下的元素，一旦发现比根部更大的元素，我们就移除堆的根，并插入这个新元素
- 第四个数是12，比1大，因此它取代了1，现在堆中的元素是
[3, 5, 12]，3成为了新的根部 - 第5个数是2，没3大，pass
- 最后一个数是11，比3大，所以取代3
之前讨论过的，从最小堆里面删除一个元素要O(logK)，我们首先往堆里面插入了K个元素，然后迭代剩余的元素，然后每一步在最坏的情况下，我们都需要进行删除插入操作，我们算法需要的复杂度为O(K∗logK+(N−K)∗logK)。很明显，这个比O(N∗logN)好多喽！
由于整体步骤都比较简单，我们直接来看代码：
public static List<Integer> findKLargestNumbers(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
// 首先向最小堆中插入K个元素
for (int i = 0; i < k; i++)
minHeap.add(nums[i]);
// 迭代数组中的剩余元素，如果他比堆中最小元素大，那么删除堆中最小的元素，把它插进去
for (int i = k; i < nums.length; i++) {
if (nums[i] > minHeap.peek()) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
//这时候留在堆里面的就是前K大元素
return new ArrayList<>(minHeap);
}
这时候我们的时间复杂度在O(N∗logK)，而因为我们只要在堆中保存元素，空间复杂度在O(K)，相比之前已经优化了很多。
不会这么简单吧？
确实如很多人所想，真实的面试题不会就这么简单，还会加入其他的限制，不过我们已经把基本理念阐述清楚了，遇到其它限制条件我们对症下药就是了。
我们来看一个更可能在面试中遇到的题目：给定一个数组跟一个数字K，从数组中移除K个元素，使得剩下最大数量不重复的数字。
示例1:
输入: [7, 3, 5, 8, 5, 3, 3], and K=2
输出: 3
解释: 移除2个3，还能有7，3，8这三个不重复的数。
示例2:
输入: [3, 5, 12, 11, 12], and K=3
输出: 2
解释: 移除一个12，此时数组里所有元素都不同，此时随便移除哪2个都可以。
示例3:
输入: [1, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5], and K=2
输出: 3
解释: 移除一个4，然后3跟5随便选一个，我们能得到3个不同的数。
我们来观察一下这些示例，我们优先选择那些出现两次的元素去删，然后再往出现次数更多的元素去删，理论上我们就能得到最多的不重复元素，为了达到这个目的，我们要找到出现频率最低的元素。那这道题看下来还是我们熟悉的配方啊，本质上还是Top K的套路，只不过我们这边比较的不是大小而是出现频率。
那我们还是遵循一个类似的步骤来解题：
- 首先确定每个元素的频率
- 然后把那些有重复的元素基于它们出现的频率放进最小堆，同时也计算不重复元素的数量
- 采用贪心策略，每次都从堆中移除出现频率最低的元素，试着去掉它重复的部分，试着把它的个数减到1，如果能减到1，那么不重复的元素就多了一个，当然了，我们删除的数量也是有限制的，超过K个就不能删了
- 如果堆中的元素都删光了，K>0，那此时只能去删除不重复元素的数量咯
看吧，尽管我们对这道题很陌生，但是一旦把它转换成我们熟悉的Top K问题，一切都变得简单起来了，?
过程也不是很复杂，我们就直接把代码写出来了：
public static int findMaximumDistinctElements(int[] nums, int k) {
int distinctElementsCount = 0;
if (nums.length <= k)
return distinctElementsCount;
// 记录每个元素出现的频率
Map<Integer, Integer> numFrequencyMap = new HashMap<>();
for (int i : nums)
numFrequencyMap.put(i, numFrequencyMap.getOrDefault(i, 0) + 1);
PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<Map.Entry<Integer, Integer>>(
(e1, e2) -> e1.getValue() - e2.getValue());
// 出现频率大于1的就要插入到堆中
for (Map.Entry<Integer, Integer> entry : numFrequencyMap.entrySet()) {
if (entry.getValue() == 1)
distinctElementsCount++;
else
minHeap.add(entry);
}
// 用贪心策略，尽可能多的让它们不重复
while (k > 0 && !minHeap.isEmpty()) {
Map.Entry<Integer, Integer> entry = minHeap.poll();
// 为了让它不重复，要把它的数目减少到1
k -= entry.getValue() - 1;
if (k >= 0)
distinctElementsCount++;
}
//如果这时候k还大于0，只能从不重复元素的数目里删了
if (k > 0)
distinctElementsCount -= k;
return distinctElementsCount;
}
我们需要往哈希表跟堆中插入所有的元素，这个时间复杂度在O(N∗logN)，N是给定数组的长度。最坏情况下，我们要从堆中删除K个元素，从堆中删除一个元素要 O(logN)，删K个就要 O(KlogN)，所以整体复杂度就在O(N∗logN+KlogN)，不过还是能再优化一下的，我们最多也只会在堆中删除K个元素，因此我们可以只往堆中插入K个元素，其余的想进来就跟堆的根部作比较，删掉一个才能新插入一个，那我们的算法就优化成O(N∗logK+KlogK)，空间复杂度比较稳定，在最坏情况下，所有元素都要往哈希表里面存，所以是O(N)。
这个也不算最花哨最难的题目，更难的我们可以以后一起见识下。我们这边主要是阐述一下遇到这种题的思路，核心思想，从哪里入手。掌握了套路我们就不慌，凡是Top K的问题，用堆找最快。遇到这样的问题我们的理念就是用好堆这个数据结构，通常我们会有最大堆，最小堆，可以通过它们来找到第k大，第k小的元素。
我们也看到这种类型的题选对数据结构很重要，在这里说白了就是看知不知道堆这个数据结构。那位同学做不出来很有可能就是不知道堆，或者是忘了堆的作用。这也是我之前强调的，在啃算法之前，先把常见的数据结构撸明白了，很多问题很多算法都需要特定的数据结构才能发挥作用，相辅相成。如果不知道那个数据结构那么大概率最后都做不出来。