Problem : To find the K largest elements in the given array.
Implementation:
- · Let us create a min heap as priority queue with a size of K.
- · Process the elements in heap. If the heap size exceeds the value of ‘K’,then the smallest element.
- · Convert the heap into array and display the two largest values.
Program:
import java.util.PriorityQueue;
public class KLargestCode {
public static
int[] identifyKLargest(int[] nos, int k) {
if (nos ==
null || nos.length == 0 || k <= 0) {
return new
int[0];
}
PriorityQueue<Integer> minHeap1 = new PriorityQueue<>(k);
//Let us process
the elements in heap
for (int no :
nos) {
minHeap1.offer(no);
// Check
whether the heap size exceeds K value,delete the smallest element
if
(minHeap1.size() > k) {
minHeap1.poll();
}
}
// make the
heap as array by converting it
int[]
resultValue = new int[k];
for (int i =
0; i < k; i++) {
resultValue[i] = minHeap1.poll();
}
return
resultValue;
}
public static void
main(String[] args) {
int[] nos =
{310, 42, 71, 5, 64, 104};
int k = 2;
int[] large =
identifyKLargest(nos, k);
System.out.println("The " + k + " largest elements
are:");
for (int no :
large) {
System.out.print(no + " ");
}
}
}
Output:
C:\raji\blog>javac KLargestCode.java
C:\raji\blog>java KLargestCode
The 2 largest elements are:
104 310
Time complexity of this solution is O(n log k). It is one of
the efficient method for this problem .Keep coding!!!
No comments:
Post a Comment