一、题目描述

链接: LeetCode 692. 前K个高频单词.

题意

给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

样例

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

复杂度要求

尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

二、思路

0、因为是打卡，用python写编程复杂度会很小，换句话说写得快。

1、字典

众所周知， python里有一个很好用的东西叫字典，我们可以用字典存下每一个字符串的出现次数，具体方法如下：

dict={
   }
def ad(self,s):
    try: self.dict[s]+=1
    except KeyError:
        self.dict[s]=1
	else : self.dict[s]+=1

注意用try检查当前字典里是否有这个字符串，没有则创建，有才能++。

2、多关键字排序

字典可以用items()转化成列表，然后通过sorted的多关键字排序即可，注意是出现次数降序，字典序升序，所以是-x[1]。

list=[]
ans=sorted(self.dict.items(), key=lambda x:(-x[1],x[0]))
for i in range(k):
	list.append(ans[i][0])

三、完整代码

class Solution:
    dict={
   }
    def ad(self,s):
        try: self.dict[s]+=1
        except KeyError:
            self.dict[s]=1
        else : self.dict[s]+=1

    def topKFrequent(self, words, k):
        self.dict.clear()
        for s in words:
            self.ad(s)
        
        list=[]
        ans=sorted(self.dict.items(), key=lambda x:(-x[1],x[0]))
        for i in range(k):
            list.append(ans[i][0])
        
        return list

四、求个关注，点赞，一键三连！谢谢！