Find the Kth Largest Element in Stream?
Link will be apear in 15 seconds.
Well done! you have successfully gained access to Decrypted Link.
Find the Kth Largest Element in Stream?
Ex:
Code:
Ex:
int arr[]={10,7,11,5,27,2,9,45};
k=3;
Output:-1 -1 7 7 10 10 10 11
Code:
import java.util.PriorityQueue; public class FindKthLargestInStream { public static void main(String[] args) { //Sorting is bad solution as it takes N^2LogN. int arr[]={10,7,11,5,27,2,9,45}; findKthLargestInStreamByMinHeap(arr,3); } //Suppose k=3 Now insert first three element of arr in pq. //Now the root element is the third largest in the pq. //Loop again from k to size of array //If the value at the root is smaller than the value in array that means the root element is no longer the //3rd largest element so therefore remove the root element and insert arr element now again root have the 3rd largest value. //Print Root //Else // Print root value //Using Priority Queue(MinHeap) O(klogk)+O(n-k)*O(logn)(for heapify) private static void findKthLargestInStreamByMinHeap(int[] arr, int k) { PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(); for (int i = 0; i < k; i++) { priorityQueue.add(arr[i]); } for (int i = 0; i < k - 1; i++) { System.out.println("-1"); } System.out.println(priorityQueue.peek()); for (int i = k; i < arr.length; i++) { if(priorityQueue.peek()<arr[i]) { priorityQueue.poll(); priorityQueue.add(arr[i]); System.out.println(priorityQueue.peek()); } else { System.out.println(priorityQueue.peek()); } } } }