前K个高频元素

2025/10/16

思路：哈希表，遍历一遍把词数存字典，最后取值前k大的。前k大的可以$O(n)$ 用锦标赛算法，而不用排序

评价：对取前k大元素理解不到位。锦标赛算法貌似不是很常见，不太好写。可以用最小堆，限制它最长为k，遇到k以上就弹出去最小值，能让操作到$O(nlogk)$。快速选择算法，是快速排序的缩水版，每次只递归一边，一遍 partition 之后右边如果大于k个，则递归右边，如果小于k个，则递归左边（但是k减掉了右边的个数），等于k个就结束。partition的过程和快速排序是一样的，都是左右两边指针往中间逼近，与partition交换，区别只在递归