Python 3 using max heap

  • 0
    import heapq
    class Solution:
        def topKFrequent(self, words, k):
            :type words: List[str]
            :type k: int
            :rtype: List[str]
            def heappush_max(heap, item):
                heapq._siftdown_max(pq, 0, len(heap)-1)
            cnt = [(-f, w) for w, f in collections.Counter(words).items()]  # O(n)
            pq = []
            for entry in cnt:  # O(nlg(k))
                heappush_max(pq, entry)
                if len(pq) > k:
            res = [heapq._heappop_max(pq)[1] for _ in range(k)]  # O(klg(k))
            return res[::-1]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.