Heap and Hashtable Solution


  • 0

    Push everything onto a hashtable first to count freq of occurrence. Then push into a max heap based on occurrence. Then pop off k elements from the max heap (this gives the top K freq elements).

    Run time analysis: O(nlogn)
    Need O(N) to iterate over hash table and O(logN) to push element onto max heap.

    def topKFrequent(self, nums, k):
        freq = collections.defaultdict(int)
        heap, res = [], []
        # store frequence of elements in hashtable
        for num in nums:
            freq[num] += 1
        # insert into heap
        for key, val in freq.iteritems():
            heapq.heappush(heap, (-val, key))
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res
    

Log in to reply
 

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