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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# return topK string
# @param strings string字符串一维数组 strings
# @param k int整型 the k
# @return string字符串二维数组
#
class Solution:
    def topKstrings(self , strings: List[str], k: int) -> List[List[str]]:
        # write code here
        map = {}
        for string in strings:
            map[string] = map.get(string, 0) + 1
        
        string_cnt_list = list(map.items())

        def compare(t1, t2):
            """
            比较两个元组大小
            t1 < t2 : True
            """
            if t1[1] < t2[1] or (t1[1] == t2[1] and t1[0] > t2[0]):
                return True
            else:
                return False
        
        def heapify(arr, k, i):
            """
            给第i个父节点构建最小堆
            """
            l = 2 * i + 1
            r = 2 * i + 2
            small = i
            if l < k and compare(arr[l], arr[small]):
                small = l
            if r < k and compare(arr[r], arr[small]):
                small = r
            if small != i:
                arr[small], arr[i] = arr[i], arr[small]
                heapify(arr, k, small)

        def buildMinHeap(arr, k):
            """
            为前k个元素构建最小堆
            """
            last_parent = (k - 1) // 2
            for i in range(last_parent, -1, -1):
                heapify(arr, k, i)

        def update(arr, t):
            """
            更新一个元素,维护最小堆
            """
            if compare(arr[0], t):
                arr[0] = t
                heapify(arr, k, 0)


        buildMinHeap(string_cnt_list, k)
        for i in range(k, len(string_cnt_list)):
            update(string_cnt_list, string_cnt_list[i])

        # 对topk排序
        for i in range(k-1, 0, -1):
            string_cnt_list[0], string_cnt_list[i] = string_cnt_list[i], string_cnt_list[0]
            heapify(string_cnt_list, i, 0)

        res = [[x[0], x[1]] for x in string_cnt_list[:k]]
        return res