We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Use 2 heaps to keep track of the median. A heap is basically a PriorityQueue in Java.
importjava.util.Scanner;importjava.util.PriorityQueue;importjava.util.Collections;// - We use 2 Heaps to keep track of median// - We make sure that 1 of the following conditions is always true:// 1) maxHeap.size() == minHeap.size()// 2) maxHeap.size() - 1 = minHeap.size()publicclassSolution{privatestaticPriorityQueue<Integer>maxHeap=newPriorityQueue<>(Collections.reverseOrder());// keeps track of the SMALL numbersprivatestaticPriorityQueue<Integer>minHeap=newPriorityQueue<>();// keeps track of the LARGE numberspublicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);intn=scan.nextInt();int[]array=newint[n];for(inti=0;i<n;i++){array[i]=scan.nextInt();}scan.close();medianTracker(array);}publicstaticvoidmedianTracker(int[]array){for(inti=0;i<array.length;i++){addNumber(array[i]);System.out.println(getMedian());}}privatestaticvoidaddNumber(intn){if(maxHeap.isEmpty()){maxHeap.add(n);}elseif(maxHeap.size()==minHeap.size()){if(n<minHeap.peek()){maxHeap.add(n);}else{minHeap.add(n);maxHeap.add(minHeap.remove());}}elseif(maxHeap.size()>minHeap.size()){if(n>maxHeap.peek()){minHeap.add(n);}else{maxHeap.add(n);minHeap.add(maxHeap.remove());}}// maxHeap will never have fewer elements than minHeap}privatestaticdoublegetMedian(){if(maxHeap.isEmpty()){return0;}elseif(maxHeap.size()==minHeap.size()){return(maxHeap.peek()+minHeap.peek())/2.0;}else{// maxHeap must have more elements than minHeapreturnmaxHeap.peek();}}}
Find the Running Median
You are viewing a single comment's thread. Return to all comments →
Java8 solution - passes 100% of test cases
Use 2 heaps to keep track of the median. A heap is basically a PriorityQueue in Java.
From my HackerRank Java solutions.