Python solution


  • 0
    P
    
    import heapq
    
    class Solution(object):
        def topKFrequent(self, words, k):
            """
            :type words: List[str]
            :type k: int
            :rtype: List[str]
            """
            max_heap_freq = list()
            hashtable = dict()
            
            # calculate the frequency of all the words
            for word in words:
                # hashtable[word] = hashtable.get(word, 0) + 1
                if hashtable.get(word, None) is None:
                    hashtable[word] = 1
                else:
                    hashtable[word] += 1
            # insert all the (word, freq) into the max_heap by comparing with values
            for word, freq in hashtable.items():
                heapq.heappush(max_heap_freq, (-freq, word))
            
            min_heap_word = [] # if the freq is same sort them by smallest alphabetical order
            result = []
            for ki in range(k):
                if len(min_heap_word) > 0 and min_heap_word[0][1] != max_heap_freq[0][0]:
                    while len(min_heap_word) > 0:
                        result.append(heapq.heappop(min_heap_word)[0])
                freq, word = heapq.heappop(max_heap_freq)
                heapq.heappush(min_heap_word, (word, freq))
            while len(min_heap_word) > 0:
                result.append(heapq.heappop(min_heap_word)[0])
            return result
                
    

Log in to reply
 

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