给一非空的单词列表，返回前k个出现次数最多的单词林大oj

题目描述

给一非空的单词列表，返回前k个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。

说明

假定k总为有效值，1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。

解题思路

首先要统计每个单词出现的次数，可以使用哈希表来完成。然后根据出现次数和字母顺序排序，可以使用优先队列来完成。

具体地，将字符串和其出现次数存储到哈希表中，然后将哈希表中的每个元素都加入到优先队列中，队列中元素按照以下规则排序：

- 如果出现次数不同，根据出现次数排序，出现次数多的在前面。
- 如果出现次数相同，根据字母顺序排序，字母靠前的在前面。

最后取出队列前k个元素的字符串即可。

时间复杂度：O(nlogk)。其中n是输入列表的长度，哈希表和优先队列的插入操作的时间复杂度均为O(logk)，总共需要插入n个元素。

空间复杂度：O(n)。哈希表存储n个单词，优先队列存储k个单词。

参考代码