leetcode 692. 前K个高频单词

题目描述：
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字母顺序 排序。

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

卡点：
1.不知道键值对可以存进堆里?
2.然后不知道堆里如何比较字母顺序

对于卡点1来说，堆不一定只能存一个数，可以放一个任何类型。这里就直接把键值对封装成一个对象放进去
对于卡点2来说，堆可以自定义比较大小的方式，然后python字符串之间用比较符实际上就是比较第一个字母的ASCII码大小，如

str1 = "abc"
str2 = "xyz"
str1>str2#返回true
1
2
3

题解：看到前k个或者第k个就联想到堆，最后题目就是用哈希表＋堆的方法，用最小堆的解法，始终让最小堆里保留k个元素，大于k了就把堆顶pop出去，这样能保证堆里面的都是最大的。最后把堆里元素取出然后翻转。

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        #堆+哈希表
        #卡点：不知道键值对可以存进堆里? 然后不知道堆里如何比较字母顺序
        dict = {}
        for i in words:
            if i in dict:
                dict[i] = dict[i]+1
            else:
                dict[i]=1
        heap = []
        for key,value in dict.items():
            heapq.heappush(heap,Node(key,value))
            if len(heap) > k:
                heapq.heappop(heap)
        res = []
        while len(heap)>0:
            tmp = heapq.heappop(heap)
            res.append(tmp.key)
        res.reverse()
        return res


class Node:
    def __init__(self,key,value):
        self.key = key
        self.value = value
    def __lt__(self,other):
        return self.key> other.key if self.value==other.value else self.value<other.value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30