Leetcode-692 前k个高频单词

这道题的解法分为两种：

1. 哈希表 + 堆
2. 前缀树

解法分类：

• 根据堆种类可分为：大顶堆（比较神奇）和小顶堆
• 根据是否改写比较方法可分为两类

解法一：哈希表 + 小顶堆

【2*哈希表 + 堆】 时间复杂度：O(3n+k)-->O(n)

import heapq

class Solution:
    # 堆如何和字典联动呢？
    def topKFrequent(self, words, k):
        di = {}
        for element in words:
            if element in di:
                di[element] += 1
            else:
                di[element] = 1
        
        heap = []
        di_nums = {}
        heapq.heapify(heap) 
        for key in di:
            heapq.heappush(heap, -di[key])
            if -di[key] in di_nums:
                di_nums[-di[key]] = di_nums[-di[key]]+','+key
            else: 
                di_nums[-di[key]] = key
                
        num_list = []
        tmp = k
        while k > 0:
            num_list.append(heapq.heappop(heap))
            k -= 1
        
        # print(num_list)
        num_list = list(set(num_list))
        num_list.sort()
        ret = []
        for e in num_list:
            if e in di_nums:
                arr = []
                if ',' in di_nums[e]:
                    arr = di_nums[e].split(',')
                    # 按字母顺序排序
                    arr.sort()
                    ret = ret + arr
                else:
                    # ret = list(ret)
                    ret.append(di_nums[e])
        
        if len(ret) > tmp:
            ret = ret[:tmp]

        return ret

解法二：改写比较函数

【大顶堆 + 改写比较函数】：O(2n+k)-->O(n)

import heapq

# 最大堆重写 __lt__ 函数 
# 参考博客：https://blog.csdn.net/weixin_43906799/article/details/112884512 和 https://www.bilibili.com/read/cv8825697?spm_id_from=333.788.b_636f6d6d656e74.26
class Solution:
    # 堆如何和字典联动呢？
    def topKFrequent(self, words, k):
        # 1.先统计词频
        mapping = {}
        for word in words:
            if word not in mapping:
                mapping[word] = 0
            mapping[word] = mapping[word]+1

        # 2.按规则放进堆里
        heap = []
        # python 字典的新写法
        for key, value in mapping.items():
            heapq.heappush(heap, Node(key, value))
            # 这是最大堆，只留下最后最小的四个，为什么留下来的一定是最小的四个，因为最大堆的堆顶是k个数里面最大的
            if len(heap) > k:
                heapq.heappop(heap)
        
        # 3. 把堆顶逐个pop出来
        ret = []
        while len(heap) > 0:
            ret.append(heapq.heappop(heap).key)
        
        ret.reverse()

        return ret


class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
    
    # costomize a comparator
    def __lt__(self, nxt):
        # Question:这个 nxt 是什么呀？
        return self.key > nxt.key if self.value == nxt.value else self.value < nxt.value

【小顶堆 + 改写比较函数】：O(2n+k)-->O(n)

import heapq

# 最小堆重写 __gt__ 函数 
# 参考博客：https://blog.csdn.net/weixin_43906799/article/details/112884512 和 https://www.bilibili.com/read/cv8825697?spm_id_from=333.788.b_636f6d6d656e74.26
class Solution:
    # 堆如何和字典联动呢？
    def topKFrequent(self, words, k):
        # 1.先统计词频
        mapping = {}
        for word in words:
            if word not in mapping:
                mapping[word] = 0
            mapping[word] = mapping[word]+1

        # 2.按规则放进堆里
        heap = []
        # python 字典的新写法
        for key, value in mapping.items():
            heapq.heappush(heap, Node(key, value))
        
        # 3. 把堆顶逐个pop出来
        ret = []
        for i in range(k):
            ret.append(heapq.heappop(heap).key)

        return ret


class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
    
    # costomize a comparator
    def __gt__(self, nxt):
        # Question:这个 nxt 是什么呀？
        return self.key > nxt.key if self.value == nxt.value else self.value < nxt.value