友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
Top 'K' Elements 顶端 K 元素
任何让我们求解最大/最小/最频繁的K个元素的题，都遵循这种模式。
用来记录这种前K类型的最佳数据结构就是堆了（译者注：在Java中，改了个名，叫优先队列（PriorityQueue））。这种模式借助堆来解决很多这种前K个数值的问题。
这个模式是这样的：
-
根据题目要求，将K个元素插入到最小堆或是最大堆。
-
遍历剩下的还没访问的元素，如果当前出来到的这个元素比堆顶元素大，那咱们把堆顶元素先删除，再加当前元素进去。
注意这种模式下，咱们不需要去排序数组，因为堆具有这种良好的局部有序性，这对咱们需要解决问题就够了。
识别最大K个元素模式：
-
如果你需要求最大/最小/最频繁的前K个元素
-
如果你需要通过排序去找一个特定的数
经典题目
Top ‘K’ Numbers (easy)
Kth Smallest Number (easy)
‘K’ Closest Points to the Origin (easy)
Connect Ropes (easy)
Top ‘K’ Frequent Numbers (medium)
Frequency Sort (medium)
Kth Largest Number in a Stream (medium)
‘K’ Closest Numbers (medium)
Maximum Distinct Elements (medium)
Sum of Elements (medium)
Rearrange String (hard)