Top K Frequent Elements
Given an integer array nums and an integer k, return the top k frequent elements in the array.
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= k <= 10^5
- It is guaranteed that the answer is unique.
Examples:
Input: [1,1,1,2,2,3] and k = 2
Output: [1,2]
Explanation: The elements 1 and 2 are the top 2 frequent elements in the array.
Solutions
Hash Table and Heap
Time: O(N log k)Space: O(N)
We use a hash table to count the frequency of each element in the array. Then we use a max heap to find the top k frequent elements.
from collections import Counter
from heapq import nlargest
def topKFrequent(nums, k):
count = Counter(nums)
return nlargest(k, count.keys(), key=count.get)Follow-up:
What if the input array is very large and does not fit into memory?
