Concise solution O(n + klogn) python using minheap and dict


  • 9
    K

    Uses a dict to maintain counts, heapifys the list of counts, then selects K elements out of the max heap.

    import heapq
    
    class Solution(object):
        def topKFrequent(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            freq = {}
            freq_list=[]  
            for num in nums:
                if num in freq:
                    freq[num] = freq[num] + 1
                else:
                    freq[num] = 1
                    
            for key in freq.keys():
               
                freq_list.append((-freq[key], key))
            heapq.heapify(freq_list)
            topk = []
            for i in range(0,k):
                topk.append(heapq.heappop(freq_list)[1])
            return topk

Log in to reply
 

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