Python bucket sort


  • 0
    A
    import collections
    import Queue
    class Solution(object):
        def topKFrequent(self, words, k):
            counter = collections.Counter(words)
            frequency = collections.defaultdict(Queue.PriorityQueue)
            limit = len(words)
            res = []
    
            for key, val in counter.items():
                frequency[val].put(key)
            
            while k > 0:
                if frequency[limit]:
                    while k > 0 and not frequency[limit].empty():
                        res.append(frequency[limit].get())
                        k -= 1
                limit -= 1
            return res
    

  • 0

    Not sure you intended to put up a O(nlogn) algorithm but this algorithm is one. If we have O(n) elements of the same frequency, each of those buckets would have O(n) elements and there for populating the heap in those buckets would take O(nlogn) time. I just wanted to point this out because if we're resorting to an O(nlogn) algorithm we can solve it with no extra space as we can do heap sort, which is an in-place sorting algorithm, then return the last k elements.


Log in to reply
 

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