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

• 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

``````

• This post is deleted!

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