Python 3 solution with O(nlogk) and O(n)


  • 9
    N
    import collections
    import heapq
    import functools
    
    @functools.total_ordering
    class Element:
        def __init__(self, count, word):
            self.count = count
            self.word = word
            
        def __lt__(self, other):
            if self.count == other.count:
                return self.word > other.word
            return self.count < other.count
        
        def __eq__(self, other):
            return self.count == other.count and self.word == other.word
    
    class Solution(object):
        def topKFrequent(self, words, k):
            """
            :type words: List[str]
            :type k: int
            :rtype: List[str]
            """
            counts = collections.Counter(words)   
            
            freqs = []
            heapq.heapify(freqs)
            for word, count in counts.items():
                heapq.heappush(freqs, (Element(count, word), word))
                if len(freqs) > k:
                    heapq.heappop(freqs)
            
            res = []
            for _ in range(k):
                res.append(heapq.heappop(freqs)[1])
            return res[::-1]
        
    

  • 0
    E

    @nychent Where does this account for words withe the same frequency, in which you then order alphabetically (ascending)


  • 0
    Y

    @emdu
    I think this part handles that.

    def __lt__(self, other):
        if self.count == other.count:
            return self.word > other.word
        return self.count < other.count
    
    def __eq__(self, other):
        return self.count == other.count and self.word == other.word

  • 0
    S

    Here's a 95% speed solution.
    (1) Use collections.Counter to collate
    (2) create list of touples containing (word,count)
    (3) Sort by the count and secondary by the word. Note that by negating the count we sort from highest count to lowest instead of the other way around. (Note also that you can't just do a reverse sort or the words themselves would be the wrong way around.)
    (4) Strip off and return a list of the first K words.

    class Solution:
        def topKFrequent(self, words, k):
            counts = collections.Counter(words)
            items = list(counts.items())
            items.sort(key=lambda item:(-item[1],item[0]))
            return [item[0] for item in items[0:k]]
    

Log in to reply
 

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