python O(nlogK) solution


  • 0
    Y

    to get logK , we need to mantain a heap of K elements, which will hold the top K elements , for the two words has same count, because the heap of python does not have a comparator, we need do some trick to keep the lower alphabetical order in the heap

        def topKFrequent(self, words, k):
            """
            :type words: List[str]
            :type k: int
            :rtype: List[str]
    
            """
            maxwordlen=0
            mp={}
            for word in words:
                maxwordlen=max(maxwordlen,len(word))
                mp[word]=mp.get(word,0)+1
            q=[]
            for key in mp:
                cmpstr=""
                for i in xrange(maxwordlen):
                    x=ord(key[i]) if i<len(key) else ord("a")-1
                    cmpstr+=chr(ord("z")-x+ord("a"))
                if len(q)<k:
                    heapq.heappush(q,(mp[key],cmpstr,key))
                elif mp[key]>q[0][0] or (mp[key]==q[0][0] and cmpstr>q[0][1]):
                    heapq.heappop(q)
                    heapq.heappush(q,(mp[key],cmpstr,key))
            res=[]
            for i in xrange(k):
                res.append(heapq.heappop(q)[2])
            return res[::-1]

Log in to reply
 

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