题解 | #字符串出现次数的TopK问题#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# return topK string
# @param strings string字符串一维数组 strings
# @param k int整型 the k
# @return string字符串二维数组
#
import heapq

# 需要自定义类，重写__lt__方法，不管是排序还是入堆，都只使用<进行比较
class MyDict:
    def __init__(self, item):
        self.item = list(item)

    def __lt__(self, other):
        if self.item[1] != other.item[1]:
            return self.item[1] < other.item[1]
		# 注意是按照字典序从小到大排序的 
        return self.item[0] > other.item[0]

class Solution:
    def topKstrings(self , strings: List[str], k: int) -> List[List[str]]:
        # write code here
        my_map = {}
        for i in strings:
            if my_map.get(i) is None:
                my_map[i] = 1
            else:
                my_map[i] += 1

        # 把字典转换成列表，并维护一个大小为K的堆
        res = []
        for item in my_map.items():
            if len(res) == k:
                heapq.heappushpop(res, MyDict(item))
            else:
                heapq.heappush(res, MyDict(item))
        temp = [heapq.heappop(res).item for _ in range(len(res))]
		# 因为是小顶堆需要反转一下
        temp.reverse()
        
        
        return temp

python3，采用堆排序的思路，使用heapq实现，时间复杂度O(nlogk)

2023.12.19 字节国际化电商测开社招一面算法题，当时用暴力破解写出来了，想到了堆排序的思路但是写不出来，寄