Python solution using priority queue, O(n log k) time, O(n) space


  • 0
    J

    If you use python2, you must change the import from queue to Queue.

    # time: O(n log k)
    # space: O(n)
    # idea: simply use priority queue
    
    import queue
    class Word:
        def __init__(self, word):
            self.word = word
            self.freq = 1
        
        def __lt__(self, other):
            # words with low frequency and high alphabetical order have high priority, as we need to delete them
            return (self.freq, other.word) < (other.freq, self.word)
    
    
    class Solution:
        def topKFrequent(self, words, k):
            """
            :type words: List[str]
            :type k: int
            :rtype: List[str]
            """
            word_dict = {}
            word_queue = queue.PriorityQueue()
            for word in words:
                if word not in word_dict:
                    word_dict[word] = Word(word)
                else:
                    word_dict[word].freq += 1
            for word in word_dict.keys():
                word_queue.put(word_dict[word])
                if word_queue.qsize() > k:
                    word_queue.get()
            ret_list = [None] * k
            # reverse the priority queue, as we need the word with highest frequency first
            for i in range(k):
                ret_list[k - 1 - i] = word_queue.get().word
            return ret_list
            
    

  • 0
    M
    This post is deleted!

Log in to reply
 

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