Top k frequent elements#

Levels: level-3

Data structures: heap, hash-table

Description#

Given a non-empty array of integers, return the k most 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.

Examples#

1Input: nums = [1,1,1,2,2,3], k = 2
2Output: [1,2]

1Input: nums = [1], k = 1
2Output: [1]

Python Solution#

 1import collections
 2import heapq
 3
 4
 5class Solution(object):
 6    def topKFrequent(self, nums, k):
 7        """
 8        :type nums: List[int]
 9        :type k: int
10        :rtype: List[int]
11        """
12        count = collections.Counter(nums)
13        return heapq.nlargest(k, list(count.keys()), key=count.get)