Problem: To find the top K frequent elements in an array.
It uses HashMap technique and a priority queue. HashMap is for counting the frequency. Priority queue is implemented as min-heap. It helps to check the top k elements.
Method:
There are two data structures and one function
Data Structures:
Priority Queue: It acts as a Min-Heap from which has the
top k frequent elements. Min-Heap is
suitable for this problem.it handles smallest frequency efficiently.
Frequency Map: It holds the count of the frequency of
each elements in the array.
Function:
It checks the heap which contains the top k frequent element
and extract it for display.
Program:
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class TopKFrequentElementsEg {
public static
int[] topKFrequent(int[] nos, int k) {
// let us
Count the frequency of each element
Map<Integer, Integer> fMap = new HashMap<>();
for (int no :
nos) {
fMap.put(no, fMap.getOrDefault(no, 0) + 1);
}
// A priority
queue (min-heap) is used to keep track of top k elements
PriorityQueue<Map.Entry<Integer, Integer>> minHeap1 = new PriorityQueue<>((a, b) ->
a.getValue() - b.getValue());
for (Map.Entry<Integer, Integer> entry :
fMap.entrySet()) {
minHeap1.offer(entry);
if
(minHeap1.size() > k) {
minHeap1.poll();
}
}
int[]
topKElements = new int[k];
int index = 0;
while
(!minHeap1.isEmpty()) {
topKElements[index++] = minHeap1.poll().getKey();
}
return
topKElements;
}
public static void
main(String[] args) {
int[] nos =
{11, 11, 11, 22, 22, 33};
int k = 2;
int[] result =
topKFrequent(nos, k);
//Let us
dispaly the result
for (int no :
result) {
System.out.print(no + " ");
}
}
}
Output:
C:\raji\blog>javac TopKFrequentElementsEg.java
C:\raji\blog>java TopKFrequentElementsEg
22 11
This is the efficient implementation of finding the top k
frequent elements in an array. Keep coding!!!
No comments:
Post a Comment