Python 3 using max heap


  • 0
    A
    import heapq
    class Solution:
        def topKFrequent(self, words, k):
            """
            :type words: List[str]
            :type k: int
            :rtype: List[str]
            """
            def heappush_max(heap, item):
                heap.append(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:
                    heapq._heappop_max(pq)
            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.