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

#
# return topK string
# @param strings string字符串一维数组 strings
# @param k int整型 the k
# @return string字符串二维数组
#
class Solution:
    def topKstrings(self , strings , k ):
        # write code here
        dic = dict()
        for s in strings:
            if s not in dic:
                dic[s] = 1
            else:
                dic[s] += 1
        lst = [list(x) for x in dic.items()]
        # 调整堆
        def maxHeapify(arr, i, heapSize):
            l = 2*i + 1
            r = l + 1
            largest = i
            if l < heapSize:
                if (arr[l][1] > arr[largest][1]) or (arr[l][1] == arr[largest][1] and arr[l][0] < arr[largest][0]):
                    largest = l
            if r < heapSize:
                if (arr[r][1] > arr[largest][1]) or (arr[r][1] == arr[largest][1] and arr[r][0] < arr[largest][0]):
                    largest = r
            if largest != i:
                arr[largest], arr[i] = arr[i], arr[largest]
                maxHeapify(arr, largest, heapSize)
        # 构建堆
        def buildMaxHeap(arr):
            for i in range(len(arr)//2-1, -1, -1):
                maxHeapify(arr, i, len(arr))
        # 堆排序
        def heapSort(arr):
            buildMaxHeap(arr)
            for i in range(len(arr)-1, 0, -1):
                arr[i], arr[0] = arr[0], arr[i]
                maxHeapify(arr, 0, i)
        heapSort(lst)
        return lst[-k:][::-1]