Hash algorithm

Leetcode 347. Top K Frequent Elements

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.
It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
You can return the answer in any order.

Answer

num_dict = {}
	for num in nums:
            if not num in num_dict:
                num_dict[num] = 1
            else:
                num_dict[num] += 1

        arr = sorted(num_dict.items(), key = lambda x: x[1], reverse=True)

        answer = [arr[i][0] for i in range(k)]
        return answer

Public Answer

from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]: 
        # O(1) time 
        if k == len(nums):
            return nums
        
        # 1. build hash map : character and how often it appears
        # O(N) time
        count = Counter(nums)   
        # 2-3. build heap of top k frequent elements and
        # convert it into an output array
        # O(N log k) time
        return heapq.nlargest(k, count.keys(), key=count.get)