347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given[1,1,1,2,2,3]and k = 2, return[1,2].

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O( n log n ), where n is the array's size.

Solution:

Time Complexity: O( n + m log k) where m is the number of unique elements, k is the parameter specified size

Steps:

1. Go thru nums array once to record the occurrence of each unique number in a hashmap
2. Create a min_heap.
3. For each key value pair in hashmap:
   1. store a tuple into heap in the format (value, key). Value will be used as comparable for heap
   2. when size(min_heap) > k, heap pop
4. return the keys of the hashmap

import heapq
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # bucket sort solution

        dic = {}
        n = len(nums)

        # O(n) time used
        for num in nums:
            if num in dic:
                dic[num] += 1
            else:
                dic[num] = 1

        # use heap to find out the top K frequent element
        # O(m log k) where m is the number of unique elements
        h = []
        for key in dic:
            heapq.heappush(h, (dic[key], key))
            while len(h) > k:
                heapq.heappop(h)


        return map(lambda tup: tup[1], h)