Mar 31
Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]Example 2:
Input: nums = [1], k = 1
Output: [1]Constraints:
1 <= nums.length <= 105kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Your algorithm’s time complexity must be better than O(n log n), where n is the array's size.
Approach 1: The idea here is to first traverse an array and create a hash map of all numbers and it’s count. The ideal data structure for storing key and value pairs is HashMap. The next step is to sort the HashMap by its value and pick only k elements.
The time complexity of this approach is O(nlogn) and its space complexity is O(n).
Approach 2: Let’s improve our previous solution using a MaxHeap using C# SortedSet<IComparer<object>>. To solve this problem first create a map of each element and its count. Then use a SortedSet to implement MaxHeap and we keep its size equal to k.
Take all the keys of a map and put them in a SortedSet. If the size of a set is greater than k, In that case, we remove the minimum element from the set. Once all the elements of HashMap are put in a set, we only get the top k elements.
The time complexity of this approach is O(nlogk) and its space complexity is O(n).
